【UOJ#340】【清华集训2017】小 Y 和恐怖的奴隶主（矩阵快速幂，动态规划）
题面
题解
考虑如何暴力\(dp\)。
设\(f[i][a][b][c]\)表示当前到了第\(i\)次攻击，还剩下的\(1,2,3\)血的奴隶主个数为\(a,b,c\)的概率，每次考虑打到了哪里，做一个转移。
这样子，状态数就是把不超过\(8\)个东西分配到\(3\)个集合中，状态有\(165\)种，再加一个状态记录糊脸上的期望，也就是\(166\)个状态。
直接矩乘优化，那么单次的复杂度就是\(O(166^3*log n)\)，显然过不了。
把\(2^k\)的矩阵预处理出来，每次拿行向量去乘矩阵，优化到\(O(166^2*log n)\)
然后就卡卡卡卡卡卡常吧。
提供几个卡常方式：
- 数组卡着数据范围开
- 随时交换循环顺序
- 手动矩乘
#include<iostream>
#include<cstdio>
using namespace std;
#define ll long long
#define MOD 998244353
void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}
inline ll read()
{
ll x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int m,K;ll n;
int bh[9][9][9],tot,lim[5];
int inv[20];
int P[61][170][170];
int A[170],tmp[170],Ans[170];
void dfs(int a,int b,int c)
{
if(a>lim[1]||b>lim[2]||c>lim[3])return;
if(bh[a][b][c]||a+b+c>K)return;
bh[a][b][c]=++tot;
dfs(a+1,b,c);dfs(a,b+1,c);dfs(a,b,c+1);
}
void Plus(int &A,int &B,int &C){if(m==1)++A;if(m==2)++B;if(m==3)++C;}
void pre()
{
inv[0]=inv[1]=1;for(int i=2;i<20;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;
for(int a=0;a<=K&&a<=lim[1];++a)
for(int b=0;a+b<=K&&b<=lim[2];++b)
for(int c=0;a+b+c<=K&&c<=lim[3];++c)
{
int s=a+b+c+1,p=bh[a][b][c];
add(P[0][p][tot+1],inv[s]);add(P[0][p][p],inv[s]);
if(a)P[0][p][bh[a-1][b][c]]=(P[0][p][bh[a-1][b][c]]+1ll*a*inv[s])%MOD;
if(b)
{
int A=a+1,B=b-1,C=c;if(s<=K)Plus(A,B,C);
P[0][p][bh[A][B][C]]=(P[0][p][bh[A][B][C]]+1ll*b*inv[s])%MOD;
}
if(c)
{
int A=a,B=b+1,C=c-1;if(s<=K)Plus(A,B,C);
P[0][p][bh[A][B][C]]=(P[0][p][bh[A][B][C]]+1ll*c*inv[s])%MOD;
}
}
add(P[0][tot+1][tot+1],1);
A[bh[m==1][m==2][m==3]]=1;
for(int p=1;p<=60;++p)
for(int i=1;i<=tot+1;++i)
for(int k=1;k<=tot+1;++k)
for(int j=1;j<=tot+1;++j)
P[p][i][j]=(P[p][i][j]+1ll*P[p-1][i][k]*P[p-1][k][j])%MOD;
}
int main()
{
int T=read();m=read();K=read();
for(int i=1;i<=m;++i)lim[i]=K;
dfs(0,0,0);pre();
while(T--)
{
n=read();int p=0;
for(int i=1;i<=tot+1;++i)Ans[i]=A[i];
while(n)
{
if(n&1)
{
for(int i=1;i<=tot+1;++i)tmp[i]=Ans[i],Ans[i]=0;
for(int k=1;k<=tot+1;++k)
for(int j=1;j<=tot+1;++j)
Ans[j]=(Ans[j]+1ll*tmp[k]*P[p][k][j])%MOD;
}
++p;n>>=1;
}
printf("%d\n",Ans[tot+1]);
}
return 0;
}