天天看点

[CSP-S2019] Emiya 家今天的饭

胡扯

时隔两年的题解...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);
}