0%

AGC038E 题解 - Gachapon

题目链接题目翻译

虽然这个容斥非常诱人,但是不管容斥硬上也是可以的。

考虑

可以观察到它应该有这样的形式

显然 $P$ 是可以大力 DP 得出的。

答案应该是

是时候拆掉 $[x^n]$ 了。设 $P_{i,j}=[x^j]P_i(x),T=\sum B$。

设后面那个东西是 $j!F_j(\dfrac{i}{S})$,也就是说

显然有 $F_0(x)=\dfrac{1}{1-x}$,递推即可。

注意特判 $x=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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
using namespace std;

const int p=998244353;
int qpow(int a,int k){
int ans=1;
while(k){
if(k&1) ans=1LL*ans*a%p;
a=1LL*a*a%p;
k>>=1;
}
return ans;
}

int N;
int fac[405],ifac[405],inv[405];
int A[405],S,iS,B[405],T;

int P[405][405];int G[405];

int main(){
fac[0]=fac[1]=ifac[0]=ifac[1]=inv[1]=1;
for(int i=2;i<=400;i++)
inv[i]=1LL*(p-p/i)*inv[p%i]%p,
fac[i]=1LL*fac[i-1]*i%p,
ifac[i]=1LL*ifac[i-1]*inv[i]%p;
scanf("%d",&N);
for(int i=0;i<N;i++) scanf("%d%d",&A[i],&B[i]),S+=A[i],T+=B[i]-1;
iS=qpow(S,p-2);

P[0][0]=1;int tS=0,tT=0;
for(int i=0;i<N;i++){
for(int j=0,mul=1;j<=B[i]-1;j++) G[j]=1LL*mul*ifac[j]%p,mul=1LL*mul*A[i]%p*iS%p;
tS+=A[i];tT+=B[i]-1;
for(int j=tS;j>=0;j--){
for(int k=tT;k>=0;k--){
int tmp=0;
for(int kk=0;kk<=B[i]-1&&kk<=k;kk++)
tmp=(tmp+1LL*G[kk]*P[j][k-kk]%p)%p;
P[j][k]=(p-tmp)%p;
}
if(j>=A[i]) for(int k=0;k<=tT;k++) P[j][k]=(P[j][k]+P[j-A[i]][k])%p;
}
}
int ans=0;
for(int i=0;i<S;i++){
int x=1LL*i*iS%p,ix=qpow(x,p-2);
int F=qpow(1-x+p,p-2),FF=F;
for(int j=0;j<=T;j++){
ans=(ans+1LL*P[i][j]*fac[j]%p*F%p)%p;
F=1LL*F*FF%p;
}
}
printf("%d\n",(p-ans)%p);
}