1 条题解

  • 0
    @ 2026-7-4 12:09:52

    #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
    上传者