容斥原理+DP 答案=没有限制3的答案-∑某一列不满足性质3的答案, 记号:行表示方案,纵表示食材
第2类: 不满足性质3的只有一种列(必须>k/2)于是求和只需枚举列超过1/2的,令枚举的这列为c
设f[i][j][k]表示前i行,第c列选j个,其余列选k个的方案数(其中s[i]表示第i行的和)
转移: f[i][j][k] = f[i-1][j][k] + a[i][c]f[i-1][j-1][k] + (s[i]-a[i][c])f[i-1][j][k-1]
优化: f[i][t]表示前i行,j-k=t的方案数,统计答案时只找t>0的 ; 初始: f[0][0] = 1
转移: f[i][t] = f[i-1][t] + a[i][c]f[i-1][t-1] + (s[i]-a[i][c])f[i-1][t+1]
第1类: 类似前面的转移;设g[i][j]表示前i行选j个的方案数 ; 初始: g[0][0] = 1
转移: g[i][j] = g[i-1][j] + s[i]*g[i-1][j-1]
点击查看代码
#include <stdio.h>
#include <string.h>
const int N = 105, M = 2e3 + 5, mod = 998244353;
typedef long long LL;
int n, m, a[N][M], s[N];
int f[N][N << 1], g[N][N];
int ans;
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
scanf("%d", &a[i][j]), (s[i] += a[i][j]) >= mod && (s[i] -= mod);
for(int c = 1; c <= m; c ++) {
memset(f, 0, sizeof(f)), f[0][n] = 1; // 由于t可能是负数,将下标+n
for(int i = 1; i <= n; i ++)
for(int t = n - i; t <= n + i; t ++)
f[i][t] = (f[i-1][t] + (LL)a[i][c] * f[i-1][t-1] % mod + LL(s[i]-a[i][c]+mod) * f[i-1][t+1] % mod) % mod;
for(int i = 1; i <= n; i ++) (ans += f[n][n + i]) >= mod && (ans -= mod);
}
(ans = mod - ans) >= mod && (ans -= mod), g[0][0] = 1;
for(int i = 1; i <= n; i ++) {
g[i][0] = g[i - 1][0];
for(int j = 1; j <= n; j ++)
g[i][j] = (g[i - 1][j] + (LL)s[i] * g[i - 1][j - 1] % mod) % mod;
}
for(int i = 1; i <= n; i ++) (ans += g[n][i]) >= mod && (ans -= mod);
printf("%d\n", ans);
return 0;
}