小 Y 和恐怖的奴隶主

一、题目

点此看题

二、解法

这道题和那个随从具体有多少血量是没有关系的，设$f[i][a][b][c]$为攻击$i$次后，一血随从数量为$a$，二血随从数量为$b$，三血随从数量为$c$，转移如下，我们讨论攻击了谁：

若$a\ne 0$，$f[i+1][a-1][b][c]=f[i][a][b][c]\times \frac{a}{a+b+c+1}$若$b\ne 0\wedge a+b+c<k$，$f[i+1][a][b-1][c+1]=f[i][a][b][c]\times \frac{b}{a+b+c+1}$若$b\ne 0\wedge a+b+c=k$，$f[i+1][a][b-1][c]=f[i][a][b][c]\times \frac{b}{a+b+c+1}$若$c\ne 0\wedge a+b+c<k$，$f[i+1][a][b+1][c]=f[i][a][b][c]\times \frac{c}{a+b+c+1}$若$c\ne 0\wedge a+b+c=k$，$f[i+1][a][b+1][c-1]=f[i][a][b][c]\times \frac{c}{a+b+c+1}$攻击$\mathtt{b}\mathtt{o}\mathtt{s}\mathtt{s}$的话，$f[i+1][a][b][c]=f[i][a][b][c]\times \frac{a}{a+b+c+1}$

$(a,b,c)$这样的组合只有$165$组，显然可以矩阵加速，还需要维护一个$\mathtt{b}\mathtt{o}\mathtt{s}\mathtt{s}$被打击的期望次数，每次累加$f[i][a][b][c]\times \frac{a}{a+b+c+1}$

因为数据组数太大，所以时间会爆炸，但是转移矩阵是一样的，我们可以预处理出转移矩阵的$2$的幂次，然后时间复杂度就变成了$O(166^3\log n+T166^2\log n)$

#include <cstdio> #include <cstring> const int M = 170; const int MOD = 998244353; #define int long long int read() { int x=0,f=1;char c; while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;} while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();} return x*f; } int T,m,k,cnt,num[10][10][10],inv[10]; struct Matrix { int n,m,a[M][M]; Matrix() {n=m=0;memset(a,0,sizeof a);} void clear() {memset(a,0,sizeof a);} Matrix operator * (const Matrix &b) const { Matrix r; r.n=n;r.m=b.m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=1;k<=b.m;k++) r.a[i][k]=(r.a[i][k]+a[i][j]*b.a[j][k])%MOD; return r; } void print() { for(int i=1;i<=n;i++,puts("")) for(int j=1;j<=m;j++) printf("%lld ",a[i][j]); } }A[65],F; void fuck3() { for(int i=0;i<=k;i++) for(int j=0;j<=k-i;j++) for(int s=0;s<=k-i-j;s++) num[i][j][s]=++cnt; cnt++; for(int i=0;i<=k;i++) for(int j=0;j<=k-i;j++) for(int s=0;s<=k-i-j;s++) { int u=num[i][j][s],iv=inv[i+j+s+1]; if(i) A[0].a[u][num[i-1][j][s]]=i*iv%MOD; if(j) { if(i+j+s<k) A[0].a[u][num[i+1][j-1][s+1]]=j*iv%MOD; else A[0].a[u][num[i+1][j-1][s]]=j*iv%MOD; } if(s) { if(i+j+s<k) A[0].a[u][num[i][j+1][s]]=s*iv%MOD; else A[0].a[u][num[i][j+1][s-1]]=s*iv%MOD; } A[0].a[u][cnt]=A[0].a[u][u]=iv; } A[0].a[cnt][cnt]=1; A[0].n=A[0].m=F.m=cnt;F.n=1; } void fuck2() { for(int i=0;i<=k;i++) for(int j=k-i;j>=0;j--) num[i][j][0]=++cnt; cnt++; for(int i=0;i<=k;i++) for(int j=k-i;j>=0;j--) { int u=num[i][j][0],iv=inv[i+j+1]; if(i) A[0].a[u][num[i-1][j][0]]=i*iv%MOD; if(j) { if(i+j<k) A[0].a[u][num[i+1][j][0]]=j*iv%MOD; else A[0].a[u][num[i+1][j-1][0]]=j*iv%MOD; } A[0].a[u][cnt]=A[0].a[u][u]=iv; } A[0].a[cnt][cnt]=1; A[0].n=A[0].m=F.m=cnt;F.n=1; } signed main() { T=read();m=read();k=read(); inv[0]=inv[1]=1; for(int i=2;i<=9;i++) inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD; if(m==3) fuck3(); else fuck2(); for(int i=1;i<=60;i++) A[i]=A[i-1]*A[i-1]; while(T--) { int n=read();F.clear(); if(m==1) F.a[1][num[1][0][0]]=1; if(m==2) F.a[1][num[0][1][0]]=1; if(m==3) F.a[1][num[0][0][1]]=1; for(int i=0;i<=60;i++) if(n&(1ll<<i)) F=F*A[i]; printf("%lld\n",F.a[1][cnt]); } }