无语了，猜猜WA哪了
头图
不要
真头图
崩坏：星穹铁道
题链 这么简单做不对不许玩崩铁！
题目大意
给你行动的总次数 \(n\) 和初始战技点数量 \(k\)，以及编队里四名角色的行动类型，求不同行动方式的方案数。
类型如下：
思路
先考虑 dp，分角色类型讨论。
设 \(f_{i,k}\) 表示第 \(i\) 动，剩 \(j\) 个点。
当 \(a=1\) 时，由于角色只能打点，点数上限为 \(5\)，所以得到：
\[f_{i,k}= \begin{cases} f_{i-1,k-1} (j\neq0) \\ f_{i-1,5} (k=5) \end{cases} \]当 \(a=2\) 时，角色有点耗点，没点打点，能得到：
\[f_{i,k}= \begin{cases} f_{i-1,k+1} (k\neq5) \\ f_{i-1,k-1} (k=1) \end{cases} \]当 \(a=3\) 时，角色既能打点，也能耗点，且满足战技点的范围，得到：
\[f_{i,k}= \begin{cases} f_{i-1,k+1} (k\neq 5) \\ f_{i-1,k-1} (k\neq0) \\f_{i-1,k} (k=5) \end{cases} \]结合三者，即可得到状态转移方程。
那么复杂度为 \(O(n)\)，题目中 \(n<=1^{18}\)，男蚌。
怎么加速？矩阵快速幂！
矩阵怎么找？简单。把不同情况的转移结果按表格列出来，发现：标 \(1\) 的是转移结果，也就是动后的点数。
结果如下：
\[T[1]=\left[ \begin{matrix} 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ \end{matrix} \right] \]\[T[2]=\left[ \begin{matrix} 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ \end{matrix} \right] \]\[T[2]=\left[ \begin{matrix} 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ \end{matrix} \right] \]其中 \(T[i]\) 表示 \(i\) 类型的角色。
再根据 dp，定义 \(C_i=C_{i-1}\times T_{a_i}\)。
这样快速幂结果为 \(ans=C_4^{\lfloor {\frac{n}{4}} \rfloor}\times C_{n \,mod \,4}\)。
答案为 \(\sum_{i=0}^5 ans_{0,i}\)。
注意
开\(\Huge{\,long\,\,long\,}\)啊！
code：
const int mod=998244353;
ll n,k,hksr;
ll a[5];
struct rmm
{
ll a[6][6];
rmm(){memset(a,0,sizeof a);}
}T[4],unit,B;
rmm operator*(const rmm &a,const rmm &b)
{//重载矩阵乘
rmm ans;
fo(i,0,5)
fo(j,0,5)
fo(k,0,5)
ans.a[i][j]=(ans.a[i][j]+a.a[i][k]*b.a[k][j]%mod)%mod;
return ans;
}
namespace Wisadel
{
rmm Wqp(rmm a,ll b)
{//矩阵快速幂
rmm ans;
ans=unit;
while(b)
{
if(b&1ll)
ans=ans*a;
a=a*a;
b>>=1ll;
}
return ans;
}
short main()
{
n=qr,k=qr;
T[1].a[0][1]=T[1].a[1][2]=T[1].a[2][3]=T[1].a[3][4]=T[1].a[4][5]=T[1].a[5][5]=1;
T[2].a[1][0]=T[2].a[0][1]=T[2].a[2][1]=T[2].a[3][2]=T[2].a[4][3]=T[2].a[5][4]=1;
T[3].a[0][1]=T[3].a[1][2]=T[3].a[2][3]=T[3].a[3][4]=T[3].a[4][5]=T[3].a[5][5]=1,
T[3].a[1][0]=T[3].a[0][1]=T[3].a[2][1]=T[3].a[3][2]=T[3].a[4][3]=T[3].a[5][4]=1;
unit.a[0][0]=unit.a[1][1]=unit.a[2][2]=
unit.a[3][3]=unit.a[4][4]=unit.a[5][5]=1;
B=unit;
//unit 是1矩阵（初始矩阵） 乘任何矩阵等于它本身
fo(i,1,4)
a[i]=qr,B=B*T[a[i]];
rmm R,ans;
R.a[0][k]=1;
ans=R*Wqp(B,n/4);
for(int i=0;i<n%4;i++)
ans=ans*T[a[i%4+1]];
//这是少算的那部分
fo(i,0,5)
hksr=(hksr+ans.a[0][i])%mod;
printf("%lld\n",hksr);
//Honkai: Star Rail！
return Ratio;
}
}
完结撒花
火~
