1 条题解
-
0

#include <cstdio> const int M = 405; const int MOD = 998244353; #define int long long #define rep(i,s,t) for(int i=(s);i<=(t);i++) int read() { int x=0,f=1;char c; while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;} while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();} return x*f; } int n,m,a[M],b[M],fac[M],inv[M],finv[M]; int ans,m1,m2,pw[M][M],dp[M][M][M]; void init(int n) { inv[0]=inv[1]=finv[0]=fac[0]=1; rep(i,1,n) fac[i]=fac[i-1]*i%MOD; rep(i,2,n) inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD; rep(i,1,n) finv[i]=finv[i-1]*inv[i]%MOD; } signed main() { n=read();init(m=400); rep(i,1,n) { m1+=a[i]=read();m2+=b[i]=read();pw[i][0]=1; rep(j,1,b[i]) pw[i][j]=pw[i][j-1]*a[i]%MOD; } dp[0][0][0]=-1; rep(i,1,n) rep(j,0,m1) rep(k,0,m2) { dp[i][j][k]=dp[i-1][j][k]; rep(l,0,b[i]-1) if(a[i]<=j && l<=k) dp[i][j][k]=(dp[i][j][k]-dp[i-1][j-a[i]][k-l] *pw[i][l]%MOD*finv[l])%MOD; } rep(j,1,m1) { int x=m1*inv[j]%MOD; rep(k,0,m2) { ans=(ans+x*fac[k]%MOD*dp[n][j][k])%MOD; x=x*inv[j]%MOD; } } printf("%lld\n",(ans+MOD)%MOD); }
- 1
信息
- ID
- 8493
- 时间
- 3000ms
- 内存
- 1024MiB
- 难度
- 10
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者