多校联测12 赌神

题目大意

你来到赌场玩游戏。有一个大箱子，里面有$n$种颜色的球，第$i$种颜色的球有$x_i$个。你可以在每种颜色的球上押上一定数量的筹码（可以是分数，但必须是有理数），需要满足总共押的筹码数不多于你当前有的筹码数。然后，箱子里就会随机出一个球，你将会获得你押在那个球的颜色的筹码数$\times n$，所有你押的筹码以及当前出来的球将会消失，直到盒子里没有球就结束了。

然而，你发现球并不是随机掉的，而是有暗箱操作的。有一个幕后黑手可以控制每一次哪一个球掉出来，而幕后黑手的使命就是使你赢的钱最少。求在双方都采取最优策略的情况下，在游戏结束后，你能够带走多少筹码。输出答案对$998244353$取模后的值。

$1\le n\le 10^6,1\le x_i\le 10^6,\sum x_i\le 10^6$

题解

我们先考虑$n=2$的情况，设$f[i][j]$表示当前你有$1$个筹码， 箱子里两种颜色的求分别有$i,j$个，你最终能够获得多少筹码。由于幕后黑手手肯定会按你得筹码最少的情况掉球，所以在最优策略下，你在不同掉球的情况下最终获得的筹码数量应该相同。设你在第一种颜色上押了$x$个筹码，则你在第二种颜色上押了$(1-x)$个筹码（易得全押比不全押更优）。那么，有

$x\cdot f[i-1][j]=(1-x)\cdot f[i][j-1]$，解得$x=\frac{f[i][j-1]}{f[i-1][j]+f[i][j-1]}$

由$f[i][j]=nx\cdot f[i-1][j]$（押了$x$个筹码，最终获得$nx$个筹码）得转移式为

$f[i][j]=\frac{nf[i-1][j]\times f[i][j-1]}{f[i-1][j]+f[i][j-1]}$

我们考虑如何优化。设$g[i][j]=\frac{f[i][j]}{n^{i+j}}$，则

$g[i][j]=\frac{g[i-1][j]\times g[i][j-1]}{g[i-1][j]+g[i][j-1]}$

两边同时取倒数，得

$\frac{1}{g[i][j]}=\frac{g[i-1][j]+g[i][j-1]}{g[i-1][j]\times g[i][j-1]}=\frac{1}{g[i-1][j]}+\frac{1}{g[i][j-1]}$

我们发现，$\frac{1}{g[i][j]}$其实就是在二维平面内，每次只能向上或向右走，从$(0,0)$到$(i,j)$的方案数，也就是$C_{i+j}^i$，于是$f[i][j]=\frac{2^{i+j}}{C_{i+j}^i}$。

考虑$n>2$时怎么做，可以发现与$n=2$的性质类似，$f(x_1,x_2,\dots ,x_n)$为$n$维平面内从$(0,0,\dots ,0)$到$(x_1,x_2,\dots ,x_n)$的方案数，即

$C_{x_1+x_2+\cdots +x_n}^{x_1}\times C_{x_2+x_3+\cdots +x_n}^{x_2}\times \cdots \times C_{x_n}^{x_n}=\frac{(\sum _{i=1}^n{c}_i)!}{x_1!(\sum _{i=2}^n{c}_i)!}\times \frac{(\sum _{i=2}^n{c}_i)!}{c_2!(\sum _{i=3}^n{c}_i)!}\times \cdots \times \frac{x_n!}{0!x_n!}=\frac{(\sum _{i=1}^n{x}_i)!}{\prod _{i=1}^n{x}_i!}$

所以$f(x_1,x_2,\dots ,x_n)=\frac{(\sum _{i=1}^n{x}_i)!}{\prod _{i=1}^n{x}_i!}$，最终的答案为$\frac{n^{x_1+x_2+\cdots +x_n}}{f_{(}{x}_1,x_2,\dots ,x_n)}$。

时间复杂度为$O(n+\sum x_i)$。

code

#include
using namespace std;
const int N=1000000;
const long long mod=998244353;
int n,sum=0,a[N+5];
long long ans=1,jc[N+5],ny[N+5];
long long mi(long long t,long long v){
	if(!v) return 1;
	long long re=mi(t,v/2);
	re=re*re%mod;
	if(v&1) re=re*t%mod;
	return re;
}
void init(){
	jc[0]=1;
	for(int i=1;i<=N;i++) jc[i]=jc[i-1]*i%mod;
	ny[N]=mi(jc[N],mod-2);
	for(int i=N-1;i>=0;i--) ny[i]=ny[i+1]*(i+1)%mod;
}
int main()
{
	init();
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		ans=ans*jc[a[i]]%mod;
		sum+=a[i];
	}
	ans=ans*ny[sum]%mod*mi(n,sum)%mod;
	printf("%lld",ans);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32