[洛谷P4007][清華集訓2017]小 Y 和恐怖的奴隸主
摘要：
最近太頹廢了，幾個星期沒A過題了，所以幾個星期都沒寫過部落格了，然後今天終於A了一道，寫了一篇部落格。
這道題首先可以想到一個DP，$f(x,i,j,k)$表示x次攻擊，達成i個1血，j個2血，k個3血的概率，然後在DP的時候統計一下答案就好了。
然後把後面三維用矩陣優化...
最近太頹廢了，幾個星期沒A過題了，所以幾個星期都沒寫過部落格了，然後今天終於A了一道，寫了一篇部落格。
這道題首先可以想到一個DP，$f(x,i,j,k)$表示x次攻擊，達成i個1血，j個2血，k個3血的概率，然後在DP的時候統計一下答案就好了。
然後把後面三維用矩陣優化掉，後面三維的實際狀態只有200個左右，我們先預處理出來所有$A^{2^k}$，然後把每次的n二進位制分解之後依次乘起來。
設矩陣是$p\times p$的，這樣子預處理的時間是$O(\lg n p^3)$的，每次詢問由於每次乘法都是向量乘矩陣，所以是$O(T\lg n p^2)$的，可以過。
#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353;
int mp[10][10][10];
typedef long long ll;
typedef int Matrix[205][205];
int top=0,m,k;
Matrix f[65];
inline void times(Matrix a,Matrix b,Matrix c){
for(register int i=0;i<top;++i)
for(register int j=0;j<top;++j)
c[i][j]=0;
for(register int i=0;i<top;++i)
for(register int k=0;k<top;++k)
if(a[i][k]!=0)
for(register int j=0;j<top;++j)
c[i][j]=((ll)a[i][k]*b[k][j]+c[i][j])%MOD;
}
inline void times2(Matrix a,Matrix b){
static Matrix c;
for(register int i=0;i<top;++i)
for(register int j=0;j<top;++j)
c[i][j]=0;
for(register int k=0;k<top;++k)
for(register int j=0;j<top;++j)
c[0][j]=((ll)a[0][k]*b[k][j]+c[0][j])%MOD;
for(register int i=0;i<top;++i)
for(register int j=0;j<top;++j)
a[i][j]=c[i][j];
}
int inv[100005];
void init(){
inv[1]=1;
for(int i=2;i<=100;++i) inv[i]=(ll)(MOD-MOD/i)*inv[MOD%i]%MOD;
int top1=(m>=1)*k,top2=(m>=2)*k,top3=(m>=3)*k;
for(int x=0;x<=top1;++x)
for(int y=0;y<=top2;++y)
for(int z=0;z<=top3;++z)
if(x+y+z<=k){
mp[x][y][z]=top++;
}
top++;
for(int x=0;x<=top1;++x)
for(int y=0;y<=top2;++y)
for(int z=0;z<=top3;++z)
if(x+y+z<=k){
int d=mp[x][y][z];
if(z>0){
int pos=x+y+z==k?mp[x][y+1][z-1]:mp[x][y+1][z];
f[0][d][pos]=(ll)z*inv[x+y+z+1]%MOD;
}
if(y>0){
int pos=x+y+z==k?mp[x+1][y-1][z]:
(m==2?mp[x+1][y][z]:mp[x+1][y-1][z+1]);
f[0][d][pos]=(ll)y*inv[x+y+z+1]%MOD;
}
if(x>0){
f[0][d][mp[x-1][y][z]]=(ll)x*inv[x+y+z+1]%MOD;
}
f[0][d][d]=inv[x+y+z+1];
f[0][d][top-1]=inv[x+y+z+1];
}
f[0][top-1][top-1]=1;
for(int p=1;p<=60;++p)
times(f[p-1],f[p-1],f[p]);
}
int query(ll n){
static int a[205][205],c[205][205];
for(int i=0;i<top;++i)
for(int j=0;j<top;++j)
a[i][j]=0;
a[0][1]=1;
for(int p=60;p>=0;--p)
if(n&(1ll<<p))
times2(a,f[p]);
return a[0][top-1];
}
int main(){
int t; scanf("%d%d%d",&t,&m,&k);
init();
while(t--){
ll n; scanf("%lld",&n);
printf("%d\n",query(n));
}
return 0;
}