首页 > 知识&问答
LuoguP4007小Y和恐怖的奴隶主
发布时间：2024-02-25 09:42:49 / 浏览量：
Link
设\(f_{i,a,b,c}\)为第\(i\)次攻击时，场上还有\(a,b,c\)个\(1,2,3\)血的随从的概率。
转移随便讨论一下就行了。
设\(g_i\)表示前\(i\)次攻击对 Boss 造成的期望伤害，转移就是\(\frac1{a+b+c+1}f_{i,a,b,c}\rightarrow g_i\)。
因为\(k\le8\)，所以实际上状态很少，总共只有\(z=166\)个。
倍增预处理转移矩阵的\(2^k\)次幂，查询时拿行向量乘上对应的转移矩阵即可，时间复杂度为\(O(z^3\log n+Tz^2\log n)\)。
#include#includeusing i64=long long;const int N=170;const i64 P=998244353,inv[]={1,1,499122177,332748118,748683265,598946612,166374059,855638017,873463809,443664157};int tot=1,st[N],id[1<<12];struct matrix{i64 a[N][N];matrix(){memset(a,0,sizeof a);}i64*operator[](int x){return a[x];}}E[60];void operator*(matrix&a,matrix&b){for(int i=0;i
4)+(s>>8))&15;E[0][i][i]=E[0][i][0]=inv[u];for(int j=0;j>(j<<2)&15) {int t=s-(1<<(j<<2));if(j+1i&1) I*E[i];printf("%lld\n",I[0]); }}
