做题记录整理dp13 P5664 [CSP-S2019] Emiya 家今天的饭（2022/9/26）

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

终于遇到一个我感觉在考场上有可做出来的题了。。。
唯一想不到的就是最开始的容斥（也就是说还是看了题解。。。），如果容斥想到的话其他其实挺自然的

#include<bits/stdc++.h>
#define for1(i,a,b) for(int i = a;i<=b;i++)
#define ll long long
#define mp(a,b) make_pair(a,b)
using namespace std;
int n,m,a[505][3005],cnt[505][3005];
ll dp[505][505],g[505][505];
const ll md=998244353;  
ll ans;
//cnt[i[[j]表示第i行的除了第i行第j个数以外的数的和
//f[i][j]表示前i行在第col行选择的数比在其他行选择的数多j个的方案数
//g[i][j]表示前ii行共选了j个数的方案数
int main()
{
cin >> n >> m;
	for1(i,1,n)
	    for1(j,1,m)
	    {
	        scanf("%d",&a[i][j]);
	        cnt[i][0] = (cnt[i][0]+a[i][j])%md;
		}
    for1(i,1,n)
        for1(j,1,m)
            cnt[i][j] = (cnt[i][0]-a[i][j]+md)%md;
 
    for1(col,1,m)//枚举非法的行 
    {
        memset(dp,0,sizeof(dp)); 
        dp[0][n] = 1;
        for1(i,1,n)//枚举每一列 
            for1(j,n-i,n+i)//因为每列只选一个，所以差值的范围应该是[-i,i],但是由于下标不能有负数，所以需要整体平移 
                dp[i][j]=(dp[i-1][j]+dp[i-1][j-1]*a[i][col]%md+dp[i-1][j+1]*cnt[i][col]%md)%md;
                //相当于前一行选j个的方案数+这一行选择第col列的数的方案数+这一行选择col列以外的数的方案数 
        for1(j,1,n)
            ans = (ans+dp[n][n+j])%md;//记录，因为每次dp数组清空（col列不同） 
	}
	
	g[0][0] = 1;
	for1(i,1,n)
	    for1(j,0,n)
	    	g[i][j] = (g[i-1][j]+(j>0?g[i-1][j-1]*cnt[i][0]%md:0))%md;
		
    for1(i,1,n)
	    ans = (ans-g[n][i]+md)%md;//记录总方案数  
	cout<<ans*(md-1)%md<<endl;//容斥 
	return 0;
}