【2023NOI模拟赛08】游戏 做题记录

罗曼诺夫跑去打炉石，发现对面很菜，所以想要计算自己一发能干掉几个。

对方有 $n$ 个随从，生命值分别是 $a_1,a_2,a_3,\dots,a_n$ 。罗曼诺夫发动一次技能，会连续攻击 $m$ 次，每次在当前生命值为正的随从中随机选择一个，使得它的生命值减 $1$。当一个随从的生命值降到 $0$ 时它就死掉了。

问期望能干掉几个随从，答案模 $998244353$ 输出。

$1\le n\le 15,1\le m,a_i\le 200,m\le \sum a_i$。

考虑按时间 dp，设 $f_{i,st}$ 表示进行了 $i$ 次操作，死掉的怪物集合是 $st$ 概率。$f_{i,st}$ 一定是形如 $\frac{AB}{n^{x}(n-1)^{y}(n-2)^{z}\dots}$ 这样的，其中 $A$ 是 $u\in st$ 的部分的方案数，$B$ 是 $u\not\in st$ 的部分的方案数。注意到 $B$ 不好计算，那么先不管它，让 $f_{i,st}$ 只计算 $\frac{A}{n^{x}(n-1)^{y}(n-2)^{z}\dots}$。

那么有 $f_{0,0}=1$，转移枚举第 $i$ 次操作伤害了哪个小怪：

• 伤害了 $u\notin st$，那么这部分的贡献属于 $B$，不管：

  $f_{i,st}\to f_{i+1,st}$

• 伤害了 $u\in st$，那么这部分的贡献属于 $A$，有：

  $\frac{f_{i,st}\times \binom{i-|st|}{a_j-1}}{(n-|st|)^{i+1}}\times (n-|st|-1)^{i+1}\to f_{i+1,st+\{j\}}$

乘的神秘次幂是为了方便计算 $\frac{1}{n^{x}(n-1)^{y}(n-2)^{z}\dots}$，注意到最后 $f_{m,st}$ 会多乘 $(n-|st|)^m$，那么进行完转移后需要让 $f_{m,st}\to \frac{f_{m,st}}{(n-|st|)^m}$。

最后需要考虑计算 $B$，可以设 $dp_{i,j}$ 表示 $u\in i$ 的怪物都没死，剩下的不管的方案数，背包转移即可。注意到这样的时间复杂度是 $O(nm2^n)$ 的，过不了，但是注意到可以 meet-in-middle 把时间复杂度变成 $O(nm2^{\lceil\frac{n}{2}\rceil})$，这样就能过了。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int N=20,M=205,BS=1<<15;
const int p=998244353;

int n,m,a[N];
int C[M][M],cnt[BS],sum[BS],mylog[BS];
int pw[M][M],qw[M][M];
int f[M][BS],dp[BS][M],pd[BS][M];

inline void add(int &x,int y)
{
	x+=y;
	if(x>=p) x-=p;
}

inline int qpow(int x,int y)
{
	int res=1;
	for(;y>0;y>>=1,x=1ll*x*x%p) res=y&1?1ll*res*x%p:res;
	return res;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	C[0][0]=1;
	for(int i=1;i<=m;i++)
	{
		C[i][0]=1;
		for(int j=1;j<=m;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%p;
	}
	for(int i=0;i<=(1<<n)-1;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(i>>j-1&1)
			{
				cnt[i]++;
				sum[i]+=a[j];
			}
		}
	}
	mylog[0]=-1;
	for(int i=1;i<=(1<<n)-1;i++) mylog[i]=mylog[i>>1]+1;
	pw[0][0]=qw[0][0]=1;
	for(int i=1;i<=m;i++)
	{
		pw[0][i]=qw[0][i]=1;
		pw[i][0]=1,qw[i][0]=1;
		int tp=qpow(i,p-2);
		for(int j=1;j<=m;j++)
		{
			pw[i][j]=1ll*pw[i][j-1]*i%p;
			qw[i][j]=1ll*qw[i][j-1]*tp%p;
		}
	}
	f[0][0]=1;
	for(int i=0;i<=m-1;i++)
	{
		for(int j=0;j<=(1<<n)-1;j++)
		{
			if(f[i][j]==0||sum[j]>i) continue;
			add(f[i+1][j],f[i][j]);
			for(int k=1;k<=n;k++)
			{
				if((j>>k-1&1^1)&&sum[j]+a[k]<=i+1)
				{
					add(f[i+1][j|(1<<k-1)],
						1ll*f[i][j]*C[i-sum[j]][a[k]-1]%p
						*qw[n-cnt[j]][i+1]%p*pw[n-cnt[j]-1][i+1]%p
					);
				}
			}
		}
	}
	for(int i=0;i<=(1<<n)-1;i++)
	{
		f[m][i]=1ll*f[m][i]*qw[n-cnt[i]][m]%p; // 除掉算多的次幂
	}
	int lim=n/2;
	dp[0][0]=1;
	for(int i=1;i<=(1<<lim)-1;i++)
	{
		int id=mylog[i&-i]+1;
		for(int j=0;j<=m;j++)
		{
			for(int k=0;k<=j&&k<a[id];k++)
			{
				add(dp[i][j],1ll*dp[i^(i&-i)][j-k]*C[j][k]%p);
			}
		}
	}
	pd[0][0]=1;
	for(int i=1;i<=(1<<n-lim)-1;i++)
	{
		int id=mylog[i&-i]+lim+1;
		for(int j=0;j<=m;j++)
		{
			for(int k=0;k<=j&&k<a[id];k++)
			{
				add(pd[i][j],1ll*pd[i^(i&-i)][j-k]*C[j][k]%p);
			}
		}
	}
	int ans=0;
	for(int i=1;i<=(1<<n)-1;i++)
	{
		if(sum[i]>m) continue;
		int stdp=(i^((1<<n)-1))&((1<<lim)-1);
		int stpd=(i^((1<<n)-1))>>lim;
		for(int j=0;j<=m-sum[i];j++)
		{
			int pre=1ll*dp[stdp][j]*pd[stpd][m-sum[i]-j]%p
			*C[m-sum[i]][j]%p
			*f[m][i]%p;
			add(ans,1ll*cnt[i]*pre%p);
		}
	}
	printf("%d\n",ans);
	return 0;
}