题解 P4007 【小 Y 和恐怖的奴隶主】

· · 题解

有一道叫做抵制克苏恩的题，本题是那道题的加强版。

那道题的做法是期望DP。

设f[i][a][b][c]表示攻击i次后，场上有a个1血随从，b个2血随从，c个三血随从的状态出现的概率。

则攻击1血随从、2血随从、3血随从、boss的概率分别为\dfrac{a}{a+b+c+1},\dfrac{b}{a+b+c+1},\dfrac{c}{a+b+c+1},\dfrac{1}{a+b+c+1}。

转移如下：

若a\neq 0，则f[i+1][a-1][b][c]+=f[i][a][b][c]\times \dfrac{a}{a+b+c+1}。

若b\neq 0：若a+b+c< k，则f[i+1][a+1][b-1][c+1]+=f[i][a][b][c]\times \dfrac{b}{a+b+c+1}，否则f[i+1][a+1][b-1][c]+=f[i][a][b][c]\times \dfrac{b}{a+b+c+1}。

若c\neq 0：若a+b+c< k，则f[i+1][a][b+1][c]+=f[i][a][b][c]\times \dfrac{c}{a+b+c+1}，否则f[i+1][a][b+1][c-1]+=f[i][a][b][c]\times \dfrac{c}{a+b+c+1}。

然后f[i+1][a][b][c]+=f[i][a][b][c]\times \dfrac{1}{a+b+c+1}，即攻击boss的情况。

记录伤害期望的话，再弄一个g数组即可。

对于本题，上面对应的就是m=3的情况，m=1和m=2的情况同理。

直接转移显然TLE。

这个东西在m=3的情况下只有165个可用状态。可以矩阵加速。

这时我们需要一个额外的状态来记录boss的扣血期望。于是最多有166个状态。

那么时间复杂度O(T166^3\log n)。

还是会TLE。

我们发现，一个行向量乘一个方阵的复杂度是O(n^2)的，而矩阵乘法满足结合律，所以考虑把2^i个方阵的乘积预处理出来，然后计算询问时，每次只要用当前的行向量乘上\log n个方阵。

这样的时间复杂度是O(166^3\log n+T166^2\log n)。

然后喜闻乐见这题卡常数，在UOJ上很可能过不了hack数据（洛谷上应该能直接过）。

有一种优化方法是减少矩阵乘法的取模次数。我每次计算的时候，直接用一个__int128来记录中间结果，这样每次加完一遍后再取模即可。

然后由于评测机的不稳定性，还是有可能TLE。

随手加几行编译指令即可QAQ

Code：

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<cstdio>
#include<cstring>
#define LL long long
#define md 998244353
#define STC static_cast<LL>
#define reg register
struct matrix{
    int a[167][167];
    int r,c;
    inline matrix(){memset(a,0,sizeof a);}
    matrix operator*(const matrix&b)const{
        matrix c;
        c.r=r,c.c=b.c;
        for(int i=0;i<r;++i)
        for(reg int j=0;j<b.c;++j){
            reg __int128 tmp=0;
            for(reg int k=0;k<b.r;++k)
            tmp+=STC(a[i][k])*b.a[k][j];
            c.a[i][j]=tmp%md;
        }
        return c;
    }
}p[62],a;
int T,m,k,num[9][9][9],inv[10];
void init3(){
    int cnt=0;
    for(int i=0;i<=k;++i)
    for(int j=k-i;~j;--j)
    for(int s=k-i-j;~s;--s)
    num[i][j][s]=cnt++;
    for(int i=0;i<=k;++i)
    for(int j=k-i;~j;--j)
    for(int s=k-i-j;~s;--s){
        int&id=num[i][j][s];
        const int ni=inv[i+j+s+1];
        if(i)p->a[id][num[i-1][j][s]]=STC(i)*ni%md;
        if(j){
            if(i+j+s<k)p->a[id][num[i+1][j-1][s+1]]=STC(j)*ni%md;else
            p->a[id][num[i+1][j-1][s]]=STC(j)*ni%md;
        }
        if(s){
            if(i+j+s<k)p->a[id][num[i][j+1][s]]=STC(s)*ni%md;else
            p->a[id][num[i][j+1][s-1]]=STC(s)*ni%md;
        }
        p->a[id][cnt]=p->a[id][id]=ni;
    }
    p->a[cnt][cnt]=1;
    p->r=p->c=cnt+1;
    a.r=1,a.c=cnt+1;
}
void init2(){
    int cnt=0;
    for(int i=0;i<=k;++i)
    for(int j=k-i;~j;--j)
    num[i][j][0]=cnt++;
    for(int i=0;i<=k;++i)
    for(int j=k-i;~j;--j){
        int&id=num[i][j][0];
        const int ni=inv[i+j+1];
        if(i)p->a[id][num[i-1][j][0]]=STC(i)*ni%md;
        if(j){
            if(i+j<k)p->a[id][num[i+1][j][0]]=STC(j)*ni%md;else
            p->a[id][num[i+1][j-1][0]]=STC(j)*ni%md;
        }
        p->a[id][cnt]=p->a[id][id]=ni;
    }
    p->a[cnt][cnt]=1;
    p->r=p->c=cnt+1;
    a.r=1,a.c=cnt+1;
}
int main(){
    inv[1]=1;
    for(int i=2;i<10;++i)
    inv[i]=STC(md-md/i)*inv[md%i]%md;
    scanf("%d%d%d",&T,&m,&k);
    if(m==3)init3();else
    init2();
    for(int i=1;i<62;++i)
    p[i]=p[i-1]*p[i-1];
    while(T--){
        LL n;
        scanf("%lld",&n);
        memset(*a.a,0,sizeof*a.a);
        if(m==1)
        a.a[0][num[1][0][0]]=1;else
        if(m==2)
        a.a[0][num[0][1][0]]=1;else
        a.a[0][num[0][0][1]]=1;
        for(int i=0;i<62;++i)
        if(n>>i&1)a=a*p[i];
        printf("%d\n",a.a[0][a.c-1]);
    }
    return 0;
}