胡扯
時隔兩年的題解...emm
由于某些原因，這裡隻講 84 和 100
題目大意
給定 n 種烹饪方法，m 種主要食材，使用第 i 種烹饪方法和第 j 道主要食材可以做出 \(a_{i,j}\) 種不同的菜。要求你做 k 道菜，滿足以下條件：
\(k\ge 1\)
每種菜使用的烹饪方法互不相同
每一種主要食材不出現超過 \(\lfloor \dfrac{n}{2}\rfloor\)次
求方案數對 \(998244353\) 取模的值。
84 pts
思路
可以發現，前兩條限制可以很簡單的滿足，問題在第三個限制上。
可以求出滿足前兩個限制的所有方案數，然後減去不滿足第三個限制的方案數。
令 \(res\) 為滿足前兩個限制的方案數。顯然， \(res = \prod \limits_{i=1}^{n}(1 + \sum \limits_{j=1}^n a_{i,j}) - 1\) 。
如何求不滿足第三個限制的方案數？
令 \(f_{i,j,k}\) 表示對于第 now 種食材，在前 \(i\) 種烹饪方法中選出了 \(j\) 次，剩餘的食材選擇了 \(k\) 次的方案數， 發現不符合第三個限制的方案即為 \(j>k\) 的情況。
可以枚舉每一個食材，記為 now 。可以發現對于一個 \(f_{i,j,k}\) 可以從以下三個狀态中轉移過來。（用 \(sum_i\) 來表示 \(\sum \limits_{j = 1}^{m} a_{i, j}\)）
\(f_{i -1, j, k}\) 即在上一次烹饪方法中沒有選任何的食材。
\(f_{i-1, j-1,k} \times a_{i, now}\) 即這次選擇了食材 now 使次數達到 j 的方案數。
\(f_{i-1, j, k-1} \times( sum_i - a_{i, now})\) 即 選擇了其他的食材使次數達到 k 的方案數。
可以發現 \(f_{i,j,k} = f_{i -1, j, k} + f_{i-1, j-1,k} \times a_{i, now}+f_{i-1, j, k-1} \times( sum_i - a_{i, now})\)。 用字首和求 \(sum\) 數組。總體複雜度是 \(\text{O}(n^3m)\) 的，不太行。
code
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 110
#define M 2010
#define ll long long
using namespace std;
const ll mod = 998244353;
int n, m; ll res, unfel;
ll a[N][M], sum[N], f[N][N][N];
int read() {
int s = 0, f = 0; char ch = getchar();
while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
return f ? -s : s;
}
int main() {
res = 1;
n = read(), m = read();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
a[i][j] = read(), sum[i] = (sum[i] + a[i][j]) % mod;
for (int i = 1; i <= n; i++)
res = res * (1ll + sum[i]) % mod;
res = (res - 1 + mod) % mod;
for (int now = 1; now <= m; now++) {
memset(f, 0, sizeof f);
f[0][0][0] = 1;
for (int i = 1; i <= n; i++)
for (int j = 0; j <= i; j++)
for (int k = 0; k <= i - j; k++) {
f[i][j][k] = f[i - 1][j][k];
if (j > 0)
f[i][j][k] = (f[i][j][k] + f[i - 1][j - 1][k]
* a[i][now] % mod) % mod;
if (k > 0)
f[i][j][k] = (f[i][j][k] + f[i - 1][j][k - 1] *
((sum[i] - a[i][now] + mod) % mod) % mod) % mod;
}
for (int j = 1; j <= n; j++)
for (int k = 0; k <= n - j; k++)
if (j > k) unfel = (unfel + f[n][j][k]) % mod;
}
printf("%lld\n", (res - unfel + mod) % mod);
}
100 pts
可以發現求解的時候隻用到了 \(j>k\) 的數，于是考慮将最後兩維優化成一維。
令 \(f_{i,j}\) 表示第 now 個食材在前 \(i\) 種烹饪方法中，選的次數與其他次數之差（可以偏移一下）。
然後我們根據上邊我們列出轉移方程就是
\[f_{i,j} = f_{i-1.j} + f_{i-1,j+1} \times(sum_i - a_{i, now}) + f_{i-1,j-1}\times a_{i,now}
\]
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 110
#define M 2010
#define ll long long
using namespace std;
const int mod = 998244353;
int n, m; ll res = 1, unfel;
ll a[N][M], sum[N], f[N][N + N];
int read() {
int s = 0, f = 0; char ch = getchar();
while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
return f ? -s : s;
}
int main() {
n = read(), m = read();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
a[i][j] = read(), sum[i] = (sum[i] + a[i][j]) % mod;
for (int i = 1; i <= n; i++)
res = res * (1ll + sum[i]) % mod;
res = (res - 1ll + mod) % mod;
for (int now = 1; now <= m; now++) {
memset(f, 0, sizeof f);
f[0][n] = 1;
for (int i = 1; i <= n; i++)
for (int j = n - i; j <= n + i; j++) {
f[i][j] = f[i - 1][j];
f[i][j] = (f[i][j] + f[i - 1][j - 1] * a[i][now] % mod) % mod;
f[i][j] = (f[i][j] + f[i - 1][j + 1] *
((sum[i] - a[i][now] + mod) % mod) % mod) % mod;
}
for (int i = 1; i <= n; i++)
unfel = (unfel + f[n][i + n]) % mod;
}
printf("%lld\n", (res - unfel + mod) % mod);
}