loj #2325. 「清华集训 2017」小Y和恐怖的奴隶主

#2325. 「清华集训 2017」小Y和恐怖的奴隶主

内存限制：256 MiB时间限制：2000 ms标准输入输出

题目类型：传统评测方式：文本比较

 

题目描述

"A fight? Count me in!" 要打架了，算我一个。

"Everyone, get in here!" 所有人，都过来！

小Y是一个喜欢玩游戏的OIer。一天，她正在玩一款游戏，要打一个Boss。

虽然这个Boss有 1010010^{100}10​100​​ 点生命值，但它只带了一个随从——一个只有 mmm 点生命值的“恐怖的奴隶主”。

这个“恐怖的奴隶主”有一个特殊的技能：每当它被扣减生命值但没有死亡（死亡即生命值 ≤0leq 0≤0），且Boss的随从数量小于上限 kkk，便会召唤一个新的具有 mmm 点生命值的“恐怖的奴隶主”。

现在小Y可以进行 nnn 次攻击，每次攻击时，会从Boss以及Boss的所有随从中的等概率随机选择一个，并扣减 111 点生命值，她想知道进行 nnn 次攻击后扣减Boss的生命值点数的期望。为了避免精度误差，你的答案需要对 998244353998244353998244353 取模。

输入格式

输入第一行包含三个正整数 T,m,kT, m, kT,m,k，TTT 表示询问组数，m,km, km,k 的含义见题目描述。

接下来 TTT 行，每行包含一个正整数 nnn，表示询问进行 nnn 次攻击后扣减Boss的生命值点数的期望。

输出格式

输出共 TTT 行，对于每个询问输出一行一个非负整数，表示该询问的答案对 998244353998244353998244353 取模的结果。

可以证明，所求期望一定是一个有理数，设其为 p/qp / qp/q（gcd(p,q)=1mathrm{gcd}(p,q) = 1gcd(p,q)=1），那么你输出的数 xxx 要满足 $\mathrm{p\equiv qx(mod998244353)。}$

样例

输入

3 2 6
1
2
3

输出

499122177
415935148
471393168

样例1解释

对于第一次询问，第一次攻击有 12frac{1}{2}​2​​1​​ 的概率扣减Boss的生命值，有 12frac{1}{2}​2​​1​​ 的概率扣减随从的生命值，所以答案为 12frac{1}{2}​2​​1​​。$\mathrm{1\equiv 2\ast 499122177(mod998244353)。}$

对于第二次询问，如果第一次攻击扣减了Boss的生命值，那么有 12frac{1}{2}​2​​1​​ 的概率第二次攻击仍扣减Boss的生命值，有 12frac{1}{2}​2​​1​​ 的概率第二次攻击扣减随从的生命值；如果第一次攻击扣减了随从的生命值，那么现在又新召唤了一个随从（“恐怖的奴隶主”），于是有 13frac{1}{3}​3​​1​​ 的概率第二次攻击扣减Boss的生命值，有 23frac{2}{3}​3​​2​​ 的概率第二次攻击扣减随从的生命值。所以答案为 12∗12∗2+12∗12∗1+12∗13∗1+12∗23∗0=1112frac{1}{2}*frac{1}{2}*2+frac{1}{2}*frac{1}{2}*1+frac{1}{2}*frac{1}{3}*1+frac{1}{2}*frac{2}{3}*0 = frac{11}{12}​2​​1​​∗​2​​1​​∗2+​2​​1​​∗​2​​1​​∗1+​2​​1​​∗​3​​1​​∗1+​2​​1​​∗​3​​2​​∗0=​12​​11​​。$\mathrm{11\equiv 12\ast 415935148(mod998244353)。}$

样例二

见附加文件下的 ex_2.in 与 ex_2.ans。

该组样例的数据范围（除询问组数 TTT 外）同第7、8个测试点。

数据范围与提示

在所有测试点中，1≤T≤1000,1≤n≤1018,1≤m≤3,1≤k≤81 leq T leq 1000, 1 leq n leq {10}^{18}, 1 leq m leq 3, 1 leq k leq 81≤T≤1000,1≤n≤10​18​​,1≤m≤3,1≤k≤8。

各个测试点的分值和数据范围如下：

测试点编号	分值	T= T=T=	n≤ nleqn≤	m= m=m=	k= k=k=
1	3	10	10	1	1
2	8			2	8
3	7		1018 {10}^{18}10​18​​		3
4	12				7
5	30	20		3	5
6	10	500			6
7	10	200			7
8	5	1000
9	10	100			8
10	5	500

/*
    f[i][a][b][c]代表剩下多少次攻击次数（abc的意义同前面）的情况下期望打几次BOSS。
    举个例子，如果你剩下0步，那么显然你一次都打不了。答案就是f[n][][][]，比如说m=3就是f[n][0][0][1]，m=2就是f[n][0][1][0]；
    那么f[i][a][b][c]由f[i-1][a'][b'][c']转移其中状态abc能推到状态a'b'c'。（比如说abc=4 1 2,a'b'c'=5 0 3）
    以上几句话是这道题的核心，期望dp倒着转移在此题得到很深刻的体现
    设计转移矩阵p[i][j]代表状态j能推到状态i的概率
    但是有一种转移f[i][a][b][c]=(f[i-1][a][b][c]+1)*(1/(a+b+c+1))无法处理，很简单，我们只需要在转移矩阵的最后一列多开一行，这行的第j列表示的是第j个状态的1/（a[j]+b[j]+c[j]+1），那么在答案矩阵的最后多开一列，这一列的第一个数为1，那么在转移的时候就会把1/（a+b+c+1）多算一次
    我们先预处理矩阵的 2^t 次方, 然后询问时相当于一堆矩阵乘一个向 量. 由于矩阵乘法具有结合性, 我们先将最右边的矩阵乘上向量, 得 到的还是一个向量, 继续这一过程即可. 
*/ 
#include<iostream>
#include<cstdio>
#include<cstring>
#define mod 998244353
using namespace std;
int p[210][210],dp[10][10][10];
int x[210],y[210],z[210],len;
int T,m,K,inv[21];
long long n;
struct node{
    int c[210][210];
    inline friend node operator * (const node a,const node b){
        node res;
        for(int i=1;i<=len;i++)
        for(int j=1;j<=len;j++){
            long long now=0;
            for(int k=1;k<=len;k++){
                now+=1LL*a.c[i][k]*b.c[k][j];
                if (now>=(long long)8e18)now%=mod;
            }
            res.c[i][j]=now%mod;
        }
        return res;
    }
    inline friend node operator + (const node a,const node b){
        node res;
        for(int i=1;i<=1;i++)
        for(int j=1;j<=len;j++){
            long long now=0;
            for(int k=1;k<=len;k++){
                now+=1LL*a.c[i][k]*b.c[k][j];
                if (now>=(long long)8e18)now%=mod;
            }
            res.c[i][j]=now%mod;
        }
        return res;
    }
}f[70],g;
inline int Pow(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=(1LL*res*a)%mod;
        a=(1LL*a*a)%mod;
        b>>=1;
    }
    return res;
}
int main(){
    freopen("Cola.txt","r",stdin);
    scanf("%d%d%d",&T,&m,&K);
    for(int i=1;i<=20;i++)inv[i]=Pow(i,mod-2);//求逆元 
    for(int i=0;i<=K;i++)
        for(int j=0;j<=K-i;j++)
            for(int k=0;k<=K-i-j;k++){//分别枚举三种生命值的随从个数，统计所有状态 
                if(m==1&&(j||k))continue;
                if(m==2&&k)continue;
                len++;x[len]=i;y[len]=j;z[len]=k;
                dp[i][j][k]=len;
            }
    len++;
    for(int i=1;i<=len;i++)//准备矩阵p[][] 
        p[len][i]=inv[x[i]+y[i]+z[i]+1];
    for(int i=1;i<len;i++)
        for(int j=1;j<len;j++)
            if(i==j)p[i][i]=inv[x[i]+y[i]+z[i]+1];
            else{
                if(z[i]){//打生命值为3的随从 
                    int xx=x[i],yy=y[i]+1,zz=z[i]-1;
                    if(xx+yy+zz<K){
                        if(m==1)xx++;
                        if(m==2)yy++;
                        if(m==3)zz++;
                    }
                    if(xx==x[j]&&yy==y[j]&&zz==z[j])p[j][i]=1LL*inv[x[i]+y[i]+z[i]+1]*z[i]%mod;
                }
                if(y[i]){//打生命值为2的随从 
                    int xx=x[i]+1,yy=y[i]-1,zz=z[i];
                    if(xx+yy+zz<K){
                        if(m==1)xx++;
                        if(m==2)yy++;
                        if(m==3)zz++;
                    }
                    if(xx==x[j]&&yy==y[j]&&zz==z[j])p[j][i]=1LL*inv[x[i]+y[i]+z[i]+1]*y[i]%mod;
                }
                if(x[i]){//打生命值为1的随从 
                    int xx=x[i]-1,yy=y[i],zz=z[i];
                    if(xx==x[j]&&yy==y[j]&&zz==z[j])p[j][i]=1LL*inv[x[i]+y[i]+z[i]+1]*x[i]%mod;
                }
            }
    for(int i=1;i<=len;i++)
        for(int j=1;j<=len;j++)
            f[0].c[i][j]=p[i][j];
    for(int i=1;i<=60;i++)f[i]=f[i-1]*f[i-1];
    while(T--){
        cin>>n;
        memset(g.c,0,sizeof(g.c));
        g.c[1][len]=1;
        for(int i=60;i>=0;i--)//一个向量与若干个矩阵相乘 
            if((1LL<<i)<=n){
                n-=1LL<<i;
                g=g+f[i];
            }
        printf("%d
",g.c[1][dp[m==1][m==2][m==3]]);
    }
    return 0;
}