题目背景
“A fight? Count me in!” 要打架了，算我一个。
“Everyone, get in here!” 所有人，都过来！
题目描述
小 Y 是一个喜欢玩游戏的 OIer。一天，她正在玩一款游戏，要打一个 Boss。
虽然这个 Boss 有 10100 点生命值，但它只带了一个随从—---一个只有 m 点生命值的 ‘‘恐怖的奴隶主’’。
这个 ‘‘恐怖的奴隶主’’ 有一个特殊的技能：每当它被扣减生命值但没有死亡（死亡即生命值 ≤ 0），且 Boss 的随从数量小于上限 k，便会召唤一个新的具有 m 点生命值的‘恐怖的奴隶主’’。
现在小 Y 可以进行 n 次攻击，每次攻击时，会从 Boss 以及 Boss 的所有随从中的等概率随机选择一个，并扣减 1 点生命值，她想知道进行 n 次攻击后扣减 Boss 的生命值点数的期望。为了避免精度误差，你的答案需要对 998244353 取模。
输入输出格式
输入格式：
从文件 patron.in 中读入数据。
输入第一行包含三个正整数 T; m; k， T 表示询问组数， m; k 的含义见题目描述。
接下来 T 行，每行包含一个正整数 n，表示询问进行 n 次攻击后扣减 Boss 的生命
值点数的期望。
输出格式：
输出到文件 patron.out 中。
输出共 T 行，对于每个询问输出一行一个非负整数，表示该询问的答案对 998244353取模的结果。
可以证明，所求期望一定是一个有理数，设其为 p/q（gcd(p; q) = 1），那么你输出的数 x 要满足 p ≡ qx (mod 998244353)。
题意：一个boss，初始带了一个小怪兽(满血为m 1->3)，你打一下小怪兽（-1）如果它没死并且当前怪兽数不超过上限k(1-9)，就会召唤另一个满血的小怪兽，或者你打一下boss对它造成1的伤害，它比较自信，不会再召唤什么奇怪的东东，求n轮（n<=1e18）对怪兽伤害的期望；
题解：
①让我们来观察一下诡异的数据范围：1e18 8 3 ，矩阵幂优化dp吧。。。。
②dp[h,i,j,k] 表示第h轮，血量为1 2 3 的怪兽个数为 i j k 的概率，再打一次伤害期望贡献为$frac{dp[h,i,j,k]}{i+j+k+1}$,同时转移到其他状态的概率是$frac{1}{i+j+k+1}$；省去h，把 dp[i,j,k] 重新定义成长度为1*tot的行矩阵，再定义一个tot*tot的矩阵，初始时tot*tot的矩阵可以dp推出，上快速幂
③统计答案，因为打怪兽和打boss是等概率的，比较方便的是再多加一位tot+1，A[tot+1][tot+1] = 1，这样就可以统计每一次的答案，最后输出ans[tot+1]即可;
④比较重要的是复杂度，根据插隔板的原理(详见白书P104) $tot = sum_{i=2}^{10}C_{i}^{2} = 165$ $O(tot^{3}log n*T)$。 倍增预处理后面的(tot+1)*(tot+1)的矩阵的2^k把复杂度里的*T换成+T*lg n就好了；
⑤卡常(心累)：其它奇技淫巧就不赘述了，主要是在矩阵乘法的时可以先用一个大数lim = k*mod(k∈Z)，超了就减去lim，最后再取模(异常缓慢的取模运算)。
1 //#pragma GCC optimize(2) 2 #include<cstdio> 3 #include<iostream> 4 #include<algorithm> 5 #include<cstring> 6 #define ll unsigned long long 7 using namespace std; 8 const int mod=998244353; 9 const ll lim=16940360401038606353llu; 10 int T,m,p,ans[170],tot,id[10][10][10],inv[20]; 11 ll n; 12 struct Mat{ 13 ll v[170][170]; 14 Mat(){memset(v,0,sizeof(v));} 15 ll *operator[](int a){return v[a];} 16 Mat operator *(const Mat &a){ 17 Mat ret; 18 for(int i=1;i<=tot+1;i++) 19 for(int j=1;j<=tot+1;j++){ 20 for(int k=1;k<=tot+1;k++){ 21 ret.v[i][j]+=v[i][k]*a.v[k][j]; 22 if(ret.v[i][j]>=lim) ret.v[i][j]-=lim; 23 } 24 ret.v[i][j]%=mod; 25 } 26 return ret; 27 } 28 }A[61];/// 29 char gc(){ 30 static char *p1,*p2,s[1000000]; 31 if(p1==p2) p2=(p1=s)+fread(s,1,1000000,stdin); 32 return(p1==p2)?EOF:*p1++; 33 }// 34 ll rd(){ 35 ll x=0; char c=gc(); 36 while(c<'0'||c>'9') c=gc(); 37 while(c>='0'&&c<='9') x=x*10+c-'0',c=gc(); 38 return x; 39 }// 40 void pre(){ 41 inv[1]=1;for(int i=2;i<=p+1;i++) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod; 42 for(int i=0;i<=p;i++) 43 for(int j=0;j<=(m>1?p-i:0);j++) 44 for(int k=0;k<=(m>2?p-i-j:0);k++) 45 id[i][j][k] = ++tot; 46 for(int i=0;i<=p;i++) 47 for(int j=0;j<=(m>1?p-i:0);j++) 48 for(int k=0;k<=(m>2?p-i-j:0);k++){ 49 int np=id[i][j][k],nk=(i+j+k<p),ni=inv[i+j+k+1]; 50 if(m==1) if(i) A[0][np][id[i-1][j][k]] = 1ll*i*ni%mod; 51 if(m==2) { 52 if(i) A[0][np][id[i-1][j][k]] = 1ll*i*ni%mod; 53 if(j) A[0][np][id[i+1][j-1+nk][k]] = 1ll*j*ni%mod; 54 } 55 if(m==3) { 56 if(i) A[0][np][id[i-1][j][k]] = 1ll*i*ni%mod; 57 if(j) A[0][np][id[i+1][j-1][k+nk]] = 1ll*j*ni%mod; 58 if(k) A[0][np][id[i][j+1][k-1+nk]] = 1ll*k*ni%mod; 59 } 60 A[0][np][np]=A[0][np][tot+1]=ni; 61 } 62 A[0][tot+1][tot+1]=1; 63 for(int i=1;i<=60;i++) A[i]=A[i-1]*A[i-1]; 64 }/// 65 void mul(int *ans,Mat M){ 66 ll ret[170]; 67 for(int j=1;j<=tot+1;j++){ 68 ret[j] = 0; 69 for(int k=1;k<=tot+1;k++) { 70 ret[j] += ans[k] * M.v[k][j]; 71 if(ret[j]>=lim) ret[j] -=lim; 72 } 73 ret[j] %= mod; 74 } 75 for(int j=1;j<=tot+1;j++) ans[j]=ret[j]; 76 }/// 77 int main() 78 { freopen("mzoj1121.in","r",stdin); 79 freopen("mzoj1121.out","w",stdout); 80 T=rd(); m=rd(); p=rd(); 81 pre(); 82 while(T--){ 83 n=rd(); 84 memset(ans,0,sizeof(ans)); 85 if(m==1) ans[id[1][0][0]]=1; 86 else if(m==2) ans[id[0][1][0]]=1; 87 else ans[id[0][0][1]]=1; 88 for(int i=60;i>=0;i--) if(n>>i&1) mul(ans,A[i]); // 89 printf("%d ",ans[tot+1]); 90 } 91 return 0; 92 }//by tkys_Austin;