萌新刚学dp求助,没过样例

P5664 [CSP-S2019] Emiya 家今天的饭

不好意思贴错代码了/kk ```cpp #include <iostream> #include <cstdio> #include <cstring> using namespace std; const int P= 998244353; #define int long long inline int read(){ register int x=0,f=0,ch=getchar(); while('0'>ch||ch>'9')f^=ch=='-',ch=getchar(); while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=getchar(); return f?-x:x; } const int MAX=45,MAXN=505; int f[MAXN][MAXN][MAXN],g[MAXN][MAXN]; // f[i][j][k] : 第 l 列,1-i 行在 l 列 j 个,其他列一共选 k 个 // f[i][j][k] = f[i-1][j][k]+a[col][i]*f[i-1][j-1][k]+(s[i]-a[col][i])*f[i-1][j][k-1] int s[MAX];// s[i]=\sum_{j=1}^{m}a[i][j] int n,m,a[MAX][MAX],ans; signed main(){ n=read(),m=read(); for(register int i=1;i<=n;++i) for(register int j=1;j<=m;++j){ a[i][j]=read(); s[i]=(s[i]+a[i][j])%P; } for(register int l=1;l<=m;++l){ memset(f,0,sizeof(f)); f[0][n][0]=1; for(register int i=1;i<=n;++i) for(register int j=1;j<=n;++j) for(register int k=1;k<=n;++k) f[i][j][k]=(f[i-1][j][k]+a[l][i]*f[i-1][j-1][k]%P+(s[i]-a[l][i])*f[i-1][j][k-1]%P)%P; for(register int j=1;j<n;++j) for(register int k=j+1;k<=n;++k) ans=(ans+f[n][j][k])%P; } g[0][0]=1; for(register int i=1;i<=n;++i){ g[i][0]=g[i-1][0]; for(register int j=1;j<=n;++j){ g[i][j]=(g[i-1][j]+s[i]*g[i-1][j-1]%P)%P; } } for(register int i=1;i<=n;++i){ ans=(ans-g[n][i])%P; } ans=(ans+P)%P; printf("%lld\n",ans); return 0; } ```
by Lates @ 2020-05-28 20:18:59


思路就是容斥吧(和第一篇题解差不多(
by Lates @ 2020-05-28 20:21:19


|