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

2020-05-09 09:25:52


可能访问不了的更好的阅读体验


看到数据范围容易想到矩阵快速幂,因此可以考虑 DP。

设 $dp_{i,a,b,c}$ 表示前 $i$ 次攻击,场上有 $a$ 个一血、 $b$ 个二血、 $c$ 个三血的概率。转移稍微讨论一下即可。

为了求答案,再设一个 $f_i$ 表示前 $i$ 次攻击对 Boss 的期望伤害,从所有 $dp_{i,a,b,c}$ 由 $\frac{1}{a+b+c+1}$ 的概率转移过来。

因为 $k\leq 8$ ,所以实际可用的状态很小,算上 $f_i$ 只有 $166$ 个。于是就可以矩阵快速幂了。

但我们每个询问都矩阵快速幂时间复杂度为 $\mathcal{O}(T166^3\log n)$ ,显然会 T。设转移矩阵为 $M$ ,考虑预处理出 $M^{2^k}$ ,则每个询问只需要拿一个行向量乘上 $\log n$ 个矩阵即可,询问时间复杂度降为 $\mathcal{O}(T166^2\log n)$ 。

另外这题有一些卡常,可以在矩乘时用 __int128 作为中间变量,最后再取模来减少取模次数。

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops,fast-math")
using namespace std;
typedef long long ll;

ll read() {
    ll X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=166+5,K=8+5;
const int mod=998244353;

int inv[N];
int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

int T,m,k;
int id[K][K][K],cnt=0;

struct Matrix {
    int s[N][N];
    Matrix() { memset(s,0,sizeof(s)); }
    int* operator [](int i) { return s[i]; }
} M[70];
Matrix operator *(Matrix a,Matrix b) {
    Matrix c;
    for (int i=1;i<=cnt;++i)
        for (int j=1;j<=cnt;++j) {
            __int128 t=0;
            for (int k=1;k<=cnt;++k) t+=1ll*a[i][k]*b[k][j];
            c[i][j]=t%mod;
        }
    return c;
}

int ans[N],tmp[N];
void Mul(int p) {
    for (int i=1;i<=cnt;++i) tmp[i]=0;
    for (int i=1;i<=cnt;++i) {
        __int128 t=0;
        for (int j=1;j<=cnt;++j) t+=1ll*ans[j]*M[p][j][i];
        tmp[i]=t%mod;
    }
    for (int i=1;i<=cnt;++i) ans[i]=tmp[i];
}

int main() {
    T=read(),m=read(),k=read();
    for (int i=1;i<=9;++i) inv[i]=qpow(i,mod-2);
    for (int a=0;a<=k;++a)
        for (int b=0;b<=(m>=2?k-a:0);++b)
            for (int c=0;c<=(m==3?k-a-b:0);++c)
                id[a][b][c]=++cnt;
    ++cnt; M[0][cnt][cnt]=1;
    for (int a=0;a<=k;++a)
        for (int b=0;b<=(m>=2?k-a:0);++b)
            for (int c=0;c<=(m==3?k-a-b:0);++c) {
                int i=id[a][b][c],iv=inv[a+b+c+1],add=a+b+c<k;
                if (m==1) {
                    if (a) M[0][i][id[a-1][b][c]]=1ll*a*iv%mod;
                }
                if (m==2) {
                    if (a) M[0][i][id[a-1][b][c]]=1ll*a*iv%mod;
                    if (b) M[0][i][id[a+1][b-1+add][c]]=1ll*b*iv%mod;
                }
                if (m==3) {
                    if (a) M[0][i][id[a-1][b][c]]=1ll*a*iv%mod;
                    if (b) M[0][i][id[a+1][b-1][c+add]]=1ll*b*iv%mod;
                    if (c) M[0][i][id[a][b+1][c-1+add]]=1ll*c*iv%mod;
                }
                M[0][i][i]=M[0][i][cnt]=iv;
            }
    for (int i=1;i<=60;++i) M[i]=M[i-1]*M[i-1];
    while (T--) {
        ll n=read();
        for (int i=1;i<=cnt;++i) ans[i]=0;
        ans[id[m==1][m==2][m==3]]=1;
        for (int i=0;i<=60;++i) if (n&(1ll<<i)) Mul(i);
        printf("%d\n",ans[cnt]);
    }
    return 0;
}