簡化版題意:

有一個 nm 列的矩陣, (i, j) 位置有 a_{i,j} 的物品,所有物品互不相同。

現從矩陣中選物品,規定每行隻能選 0/1 個物品,

且若共選瞭 k 個物品,則每列選的物品數 le lfloor frac{k}{2} rfloor ,且一共最少選 1 個物品。

問方案數

數據范圍:

n in [1,100], m in [1,2000]

解法:

發現直接做不太好求,於是從反面考慮,即:所求方案數 = 每行最多選 1 個,且可能有列上所選物品個數大於總個數的一半 的方案數 – 每行最多選 1 個,且一定有某列上所選物品個數大於總個數的一半 的方案數(容斥原理)

先考慮每行最多選一個物品的方案數,發現這是一個經典的分步計數問題,令第 i 行總物品數為 s_i ,則在第 i 行的方案數為 (s_i + 1) (+1是考慮瞭不選的情況),於是總方案數為 [quad prod _{i=1}^n (s_i+1) quad] – 1 (不能選 0 個物品,所以 -1

再考慮每行最多選一個物品,且存在一列上所選物品嚴格大於所選物品總數一半的方案數 ,易見這樣的列最多隻有 1 列,於是考慮枚舉,問題變成 求每行最多選一個物品,且第 j 列所選物品數超過總所選物品數一半 的方案數。

考慮 dp ,若當前枚舉到第 col 列上所選物品超過一半,定義 f_{i,j} 表示考慮前 i 行,且第 col 列上選擇的物品比其他列所選物品多 j 個的方案數,轉移方程:

f_{i,j} = f_{i-1,j} + f_{i-1,j-1} times a_{i,col} + f_{i-1,j+1} times (s_i-a[i][col])

解釋:考慮第 i 行選則的物品,若不選,則問題變成 f_{i-1, j} (參考定義),若選的是第 col 列的物品,則問題變成前 i-1 行,第 j 列所選物品比其他列多 j-1 個的方案數,由乘法原理,求得貢獻,若選不是第 col 列的物品,分析過程類似。

於是對於第 col 列,他會使得答案減去 sum_{j=1}^n f_{n,j}

考慮所有列後即可求得答案

Code:

#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using ll = long long;
const int N = 105, M = 2010, P = 998244353;

ll f[N][M << 1], a[N][M], s[N];

int main() {
ios
int n, m;
cin >> n >> m;
ll ans = 0, g = 1;
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++)
cin >> a[i][j], (s[i] += a[i][j]) %= P;
g = g * (s[i] + 1) % P;
}
g = (g - 1 + P) % P;
ans = g;
for(int col = 1; col <= m; col ++){
memset(f, 0, sizeof f);
f[0][n] = 1;
for(int i = 1; i <= n; i ++){
ll rest = s[i] - a[i][col];
if(rest < 0) rest += P;
for(int j = n - i; j <= n + i; j ++){
f[i][j] = f[i - 1][j] + a[i][col] * f[i - 1][j - 1] % P
+ f[i - 1][j + 1] * rest % P;
f[i][j] %= P;
}
}
for(int j = n + 1; j <= n << 1; j ++)
ans = (ans - f[n][j] + P) % P;
}
cout << ans;

return 0;
}

相关推荐阅读: