题目链接
首先dp很显然，\(f(i,s)\)表示到了第i轮，各种血量人数的情况为s今后的期望攻击boss次数。那么有\(f(i,s)=\frac{1}{num+1}*\sum_{s->s'}(f(i+1,s')+0/1)\)，num为奴隶主个数，当攻击boss时后面的贡献就是1，否则是0，s可以用一个m位k+1进制数来表示(代表血量为1,2,3的奴隶主个数)。
然后处理出s的转移需要哪些状态(总状态数为\(tot=C_{10}^2+C_9^2+...+C_2^2=165\))，那么可以矩乘优化了。由于有多组询问，因此可以预处理出矩阵的\(2^k\)次方，但由于这样做询问时的复杂度还是\(O(tot^3logn)\)的，我们想到最边上的矩阵是\(tot*1\)的，且一个\(tot*tot\)的矩阵与\(tot*1\)的矩阵乘出来还是\(tot*1\)的，因此可以从\(tot*1\)的矩阵开始一路向左乘，这样复杂度就是\(O(tot^2logn)\)的。
总复杂度\(O(tot^3logn+T*tot^2logn)\)，矩乘那里需要卡卡常。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#define P puts("lala")
#define cp cerr<<"lala"<<endl
#define ln putchar('\n')
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
inline int read()
{
char ch=getchar();int g=1,re=0;
while(ch<'0'||ch>'9') {if(ch=='-')g=-1;ch=getchar();}
while(ch<='9'&&ch>='0') re=(re<<1)+(re<<3)+(ch^48),ch=getchar();
return re*g;
}
typedef long long ll;
typedef pair<int,int> pii;
const int N=201;
const int mod=998244353;
const ll MOD=(0x7fffffffffffffffll/mod-mod)*mod;
const ll MAXN=1e18;
const int maxb=59;
ll qpow(ll a,int n)
{
ll ans=1;
for(;n;n>>=1,a=a*a%mod) if(n&1) ans=ans*a%mod;
return ans;
}
struct mat
{
int n,m;
int s[169][169];
mat() {clean();}
void clean() {memset(s,0,sizeof(s));n=m=0;}
};
mat c;
ll tmp[169][169];
mat operator * (const mat &a,const mat &b)
{
c.n=a.n; c.m=b.m;
for(int i=0;i<a.n;++i) for(int k=0;k<a.m;++k)
{
if(!a.s[i][k]) continue;
for(int j=0;j<b.m;++j) if((tmp[i][j]+=1ll*a.s[i][k]*b.s[k][j])>=MOD)
tmp[i][j]-=MOD;
//c.s[i][j]=(c.s[i][j]+1ll*a.s[i][k]*b.s[k][j]%mod)%mod;
}
for(int i=0;i<c.n;++i) for(int j=0;j<c.m;++j)
c.s[i][j]=tmp[i][j]%mod,tmp[i][j]=0;
return c;
}
mat matpw[70],X,V;
int id[N],is[N],tot=0,pw[15],K,m,k;
ll n;
void wj()
{
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
}
int main()
{
wj();
int i,j,opt,T;
T=read(); m=read(); k=read();
K=k+1; pw[0]=1;
for(i=1;i<=m;++i) pw[i]=pw[i-1]*K;
for(i=0;i<pw[m];++i)
{
int s=0;
for(j=0;j<m;++j) s+=i/pw[j]%K;
if(s<=k) is[tot]=i,id[i]=tot,tot++;
}
X.n=tot+1; X.m=1;
X.s[tot][0]=1;
matpw[0].n=matpw[0].m=tot+1;
matpw[0].s[tot][tot]=1;
for(int idx=0;idx<tot;++idx)
{
int num=0;
for(i=0;i<m;++i) num+=is[idx]/pw[i]%K;
int inv=qpow(num+1,mod-2);
matpw[0].s[idx][tot]=inv; matpw[0].s[idx][idx]=inv;
int x=is[idx];
for(i=0;i<m;++i) if(x/pw[i]%K)
{
x-=pw[i];
if(i) x+=pw[i-1];
if(i&&num<k) x+=pw[m-1];
(matpw[0].s[idx][id[x]]+=1ll*inv*(is[idx]/pw[i]%K)%mod)%=mod;
x=is[idx];
}
}
for(i=1;i<=maxb;++i) matpw[i]=matpw[i-1]*matpw[i-1];
int ans=pw[m-1];
for(int cas=1;cas<=T;++cas)
{
scanf("%lld",&n);
V=X;
for(i=0;i<=maxb;++i) if(n&(1ll<<i)) V=matpw[i]*V;
printf("%d\n",V.s[id[ans]][0]);
}
return 0;
}
