[AGC038E] Gachapon

Problem Statement

Snuke found a random number generator. It generates an integer between $0$ and $N-1$ (inclusive). An integer sequence $A_0, A_1, \cdots, A_{N-1}$ represents the probability that each of these integers is generated. The integer $i$ ($0 \leq i \leq N-1$) is generated with probability $A_i / S$, where $S = \sum_{i=0}^{N-1} A_i$. The process of generating an integer is done independently each time the generator is executed.

Now, Snuke will repeatedly generate an integer with this generator until the following condition is satisfied:

• For every $i$ ($0 \leq i \leq N-1$), the integer $i$ has been generated at least $B_i$ times so far.

Find the expected number of times Snuke will generate an integer, and print it modulo $998244353$. More formally, represent the expected number of generations as an irreducible fraction $P/Q$. Then, there exists a unique integer $R$ such that $R \times Q \equiv P \pmod{998244353},\ 0 \leq R < 998244353$, so print this $R$.

From the constraints of this problem, we can prove that the expected number of generations is a finite rational number, and its integer representation modulo $998244353$ can be defined.

$N$
$A_0$ $B_0$
$A_1$ $B_1$
$\vdots$
$A_{N-1}$ $B_{N-1}$

2
1 1
1 1

3

3
1 3
2 2
3 1

971485877

15
29 3
78 69
19 15
82 14
9 120
14 51
3 7
6 14
28 4
13 12
1 5
32 30
49 24
35 23
2 9

371626143

要求最晚的一个被填满的时间，是很难求的。考虑min-max反演，把他转变为求第一个被填到的时间。

现在要求每一个集合的第一个被填到 \(b_i\) 的时间，枚举这个是那个点，然后我们就知道这个序列中最后一个被填的是哪一个（设为给 d加了1）。那其他点呢？我们需要结束时这个点的状态，把他设为 \(c_i\)，那么对于一个固定的 \(c\)，在选的顺序上有 \(\frac{(\sum c_i)!}{\prod c_i!}\) 种，刚好会选出这些数的概率是 \(\tfrac{\prod a_i^{c_i}}{S^{\sum c_i}}\)，最后刚好选到 d 的概率是 \(\frac dS\)。这些都是集合内的概率，而期望下在 \(\frac S{\sum a_i}\) 会抽到一次集合内的数，则再乘一个 \(\frac S{\sum a_i}(\sum c+1)\)。汇总一下式子

到这里就可以dp了，定义 \(dp_{i,j,k,0/1,0/1}\) 为集合中前 \(i\) 个数，c之和为 j，a之和为k，容斥系数和是否选出d

对于某一个集合，我们需要dp才能解决，那么对于所有的集合，我们也可以通过dp来解决，只不过多了一种不选入集合的情况

虽然枚举加 dp 是四维的，但是 \(\sum b\le 400\)，所以总共也是 \(n^3\)

#include<bits/stdc++.h>
using namespace std;
const int N=405,P=998244353;
int n,a[N],b[N],f[N],iv[N],dp[N][N][2][2],sa,sb,inv[N],ans;
int pown(int x,int y)
{
	if(!y)
		return 1;
	int t=pown(x,y>>1);
	if(y&1)
		return 1LL*t*t%P*x%P;
	return 1LL*t*t%P;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d",a+i,b+i);
	for(int i=inv[1]=iv[0]=f[0]=1;i<=400;i++)
	{	
		f[i]=1LL*f[i-1]*i%P;
		if(i^1)
			inv[i]=1LL*(P-P/i)*inv[P%i]%P;
		iv[i]=1LL*iv[i-1]*inv[i]%P;
	}
	dp[0][0][0][0]=1;
	for(int i=1;i<=n;i++)
	{
		sa+=a[i];
		sb+=b[i];
		for(int j=sa;j>=a[i];j--)
		{
			for(int k=sb;k>=0;k--)
			{
				long long pw=1,lp;
				for(int c=0;c<b[i]&&c<=k;c++,pw=1LL*pw*a[i]%P)
				{
					lp=pw;
					(dp[j][k][0][0]+=dp[j-a[i]][k-c][1][0]*pw%P*iv[c]%P)%=P;
					(dp[j][k][1][0]+=dp[j-a[i]][k-c][0][0]*pw%P*iv[c]%P)%=P;
					(dp[j][k][1][1]+=dp[j-a[i]][k-c][0][1]*pw%P*iv[c]%P)%=P;
					(dp[j][k][0][1]+=dp[j-a[i]][k-c][1][1]*pw%P*iv[c]%P)%=P;
				}
				if(k>=b[i]-1)
				{
					(dp[j][k][0][1]+=pw*dp[j-a[i]][k-b[i]+1][1][0]%P*iv[b[i]-1]%P)%=P;
					(dp[j][k][1][1]+=pw*dp[j-a[i]][k-b[i]+1][0][0]%P*iv[b[i]-1]%P)%=P;
				}
			}
		}
	}
	for(int i=0;i<=sa;i++)
	{
		for(int j=0;j<=sb;j++){
			(ans+=1LL*(P-1)*dp[i][j][0][1]%P*(j+1)%P*inv[i]%P*f[j]%P*inv[i]%P*pown(pown(i,j),P-2)%P)%=P;
			(ans+=1LL*dp[i][j][1][1]*(j+1)%P*inv[i]%P*f[j]%P*inv[i]%P*pown(pown(i,j),P-2)%P)%=P;
		}
	}
	printf("%lld\n",ans*1LL*sa%P);
}