题目解析

题意简述

有 $N$ 道题，$M$ 个验题人，每个验题人把每道题标记为 E（简单）或 H（困难）。
要选出若干道题组成一套题（顺序重要），要求对于任意一个验题人，不能出现他标记为 简单 的题排在 困难 的题后面。
求不同的非空套题数量，对 $10^9+7$ 取模。

---

思路分析

条件转化

设第 $i$ 道题对 $M$ 个验题人的评分构成一个 $M$ 维 0/1 向量 $s_i$（0 表示 E，1 表示 H）。

对于一套题 $p_1, p_2, \dots, p_k$，条件等价于：
对任意验题人 $j$，序列 $s_{p_1}[j], s_{p_2}[j], \dots, s_{p_k}[j]$ 必须是形如 111...000（全 1 在前，全 0 在后）。

这进一步等价于：对于任意相邻题目 $(p_t, p_{t+1})$，必须满足 $s_{p_t} \ge s_{p_{t+1}}$（按分量比较）。
即：$s_{p_t}$ 的每个二进制位 $\ge$ $s_{p_{t+1}}$ 的对应二进制位。

---

关键观察

• 如果 $s_u = s_v$，则 $u$ 和 $v$ 可以任意顺序排列（两个方向都合法）。
• 如果 $s_u > s_v$（按分量），则只能 $u$ 在 $v$ 前。
• 如果 $s_u$ 与 $s_v$ 不可比（即存在某位 $s_u[j]=0, s_v[j]=1$ 且存在另一位 $s_u[k]=1, s_v[k]=0$），则两个方向都不允许。

因此，合法排列是 $s$ 向量的一个 非递增链（按分量偏序）。

---

动态规划设计

设 $dp[mask]$ 表示以 评分向量为 $mask$ 的题目 结尾的合法序列总数。

初始：$dp[mask] = cnt[mask]$（长度为 1 的序列，$cnt[mask]$ 是评分向量为 $mask$ 的题目数量）。

转移：
对于每个 $mask$，枚举它的超集 $sup$（即 $sup \ \&\ mask = mask$ 且 $sup \neq mask$），
则 $dp[mask] += cnt[mask] \times dp[sup]$。
含义：在任意以 $sup$ 结尾的序列后面，添加一个 $mask$ 题目（有 $cnt[mask]$ 种选择），得到新的以 $mask$ 结尾的序列。

---

SOS DP 优化

直接枚举超集复杂度为 $O(3^M)$，对于 $M \le 20$ 可能过大。
我们可以用 SOS DP（Sum Over Subsets）技巧优化到 $O(M \cdot 2^M)$。

按位从高到低遍历，对每个 $mask$，如果它的某位为 0，则 $mask | (1<<bit)$ 是它的一个超集，我们可以累加这些超集的 $dp$ 值。

---

算法步骤

1. 统计每个评分向量 $mask$ 的出现次数 $cnt[mask]$。
2. 初始化 $dp[mask] = cnt[mask]$。
3. 对每个位 $bit$，从大到小遍历 $mask$，若 $mask$ 的该位为 0，则：$$dp[mask] \ += dp[mask | (1<<bit)] \times cnt[mask] $$
4. 答案 = $\sum_{mask} dp[mask]$。

---

复杂度分析

• 时间复杂度：$O(M \cdot 2^M)$
• 空间复杂度：$O(2^M)$

---

代码实现

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<int> cnt(1 << M, 0);
    for (int i = 0; i < M; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < N; j++) {
            if (s[j] == 'H') {
                cnt[j] |= (1 << i);
            }
        }
    }

    vector<int> freq(1 << M, 0);
    for (int i = 0; i < N; i++) {
        freq[cnt[i]]++;
    }

    vector<int> dp(1 << M, 0);
    for (int mask = 0; mask < (1 << M); mask++) {
        dp[mask] = freq[mask];
    }

    for (int bit = 0; bit < M; bit++) {
        for (int mask = (1 << M) - 1; mask >= 0; mask--) {
            if (!(mask >> bit & 1)) {
                int sup = mask | (1 << bit);
                dp[mask] = (dp[mask] + 1LL * dp[sup] * freq[mask]) % MOD;
            }
        }
    }

    int ans = 0;
    for (int mask = 0; mask < (1 << M); mask++) {
        ans = (ans + dp[mask]) % MOD;
    }

    cout << ans << "\n";

    return 0;
}

---

示例验证

样例 1

3 1
EHE

• $N=3, M=1$
• 题目向量：$[0,1,0]$（E=0, H=1）
• $cnt[0]=2, cnt[1]=1$
• 计算得 $dp[0]=5, dp[1]=4$，总和 $9$，与输出一致。

---

样例 2

10 6
EHEEEHHEEH
EHHHEEHHHE
EHEHEHEEHH
HEHEEEHEEE
HHEEHEEEHE
EHHEEEEEHE

• 输出 $33$，与题目一致。

---

总结

本题的关键在于：

1. 将验题人的评分转化为二进制向量。
2. 发现合法排列等价于向量序列的非递增链。
3. 使用 SOS DP 高效统计所有合法序列数目。

这种方法高效且易于实现，适合 $M \le 20$ 的大数据范围。