解析

應該是比較入門的容斥了
統計方案用總方案數-某列超過1半的方案數
dp設計的一個trick是只統計差值

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long const int N=2050; const double eps=1e-6; const int mod=998244353; inline ll read(){ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return f*x; }int n,m; ll f[2][2050][205],g[105][2050]; ll a[105][2050],sum[105],o; int main(){ #ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout); #endifn=read();m=read();o=n+2;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){a[i][j]=read();sum[i]+=a[i][j];sum[i]%=mod;}}ll ans=0;int now;g[0][0]=1;for(int i=1;i<=n;i++){g[i][0]=1;for(int j=1;j<=i;j++) g[i][j]=(g[i-1][j]+g[i-1][j-1]*sum[i])%mod;}for(int j=1;j<=m;j++){now=0;f[0][j][0+o]=1;for(int i=1;i<=n;i++){now^=1;for(int k=-i;k<=i;k++){f[now][j][k+o]=(f[now^1][j][k-1+o]*a[i][j]+f[now^1][j][k+o]+f[now^1][j][k+1+o]*(sum[i]-a[i][j]))%mod; }}}for(int i=1;i<=n;i++) (ans+=g[n][i])%=mod;for(int j=1;j<=m;j++){for(int k=1;k<=n;k++) ans=(ans-f[n&1][j][k+o]+mod)%mod;}printf("%lld\n",ans);return 0; } /*4a1 22 31 33 4 */

總結

以上是生活随笔為你收集整理的洛谷P5664：Emiya 家今天的饭（容斥、dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。