题解：P9131 [USACO23FEB] Problem Setting P

· · 题解

我们把每一列看作一个行编号的集合 S_i，即若 a_{j, i} = \texttt H 则 j \in S_i。那么一个序列 (i_1,i_2,\dots,i_k) 合法，等价于 S_{i_1} \subseteq S_{i_2} \dots \subseteq S_{i_k}。

尝试 DP 这个东西：设 f(S) 表示有多少合法序列以 S 结尾。那么：

f(S) = g(cnt_S) \times \sum_{S' \subseteq S} f(S')

其中 cnt_S 表示 S 出现的次数（在所有列中）。g(x) 表示从 x 中任选若干个数，并任意排列的方案数。不难得出：

\begin{aligned} g(x) &= \sum_{i=1}^x A_x^i \\ &= \sum_{i=1}^x \dfrac {x!}{i!} \\ &= 1 + \sum_{i=1}^{x-1} \dfrac{(x-1)! \times x}{i!}\\ &= 1 + x \times g(x - 1) \end{aligned}

我们一层一层转移，即按照 |S| 转移。那么这一层的转移，等价于之前的层的 DP 值的高维前缀和。

#include <bits/stdc++.h>

using namespace std;

const int N = 4e6 + 10, P = 1e9 + 7;

int n, m;
int s[N];         
int f[N], g[N];
int cnt[N];
vector<int> state[N];
int sum[N];

int main() {
  g[0] = 0;
  g[1] = 1;
  for (int i = 2; i < N; ++ i ) {
    g[i] = (1ll * i * (g[i - 1] + 1) % P) % P;
  }

  cin >> n >> m;

  for (int i = 0; i < m; ++ i ) {
    for (int j = 0; j < n; ++ j ) {
      char c;
      cin >> c;
      s[j] |= (c == 'H') << i;
    }
  }

  for (int i = 0; i < n; ++ i ) {
    cnt[s[i]] ++ ;
  }

  for (int i = 0; i < (1 << m); ++ i )
    state[__builtin_popcount(i)].push_back(i);

  f[0] = g[cnt[0]];
  for (int i = 1; i <= m; ++ i ) {

    for (int j = 0; j < (1 << m); ++ j ) sum[j] = f[j];
    for (int j = 0; j < m; ++ j )
      for (int k = 0; k < 1 << m; ++ k )
        if (k >> j & 1) sum[k] = (sum[k] + sum[k ^ (1 << j)]) % P;

    for (int k : state[i]) {
      f[k] = 1ll * (sum[k] + 1) * g[cnt[k]] % P;
    }
  }

  int res = 0;
  for (int i = 0; i < (1 << m); ++ i ) {
    res = (res + f[i]) % P;
  }
  cout << res;

  return 0;
}