T2-14 修复古老的预言

题意理解

有 $N$ 卷羊皮纸，每卷长度为 $L$。要从中拼出目标串 $T$，规则是：每次选取字符时，列下标必须严格递增（但可以来自任意一卷羊皮纸）。求方案数。

---

思路分析

关键观察： 列下标必须严格递增，意味着每一列最多只能贡献 $T$ 的一个字符。

使用动态规划，按列从左到右遍历。

设 $dp[i]$ 表示：已经匹配了 $T$ 的前 $i$ 个字符的方案数。

对于第 $k$ 列，预处理 $cnt[c]$ = 该列字符 $c$ 在所有羊皮纸中出现的次数。

状态转移（倒序枚举，避免同一列重复使用）：

$$dp[i] = dp[i] + dp[i-1] \times cnt[T[i-1]]$$

边界条件：

• $dp[0] = 1$：还没匹配任何字符，方案数为 1

答案： $dp[|T|]$

---

参考代码

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

const int MOD = 1e9 + 7;  // 模数
const int MAXN = 1005;    // 最大长度

int N, L;                 // 羊皮纸数量和长度
char paper[MAXN][MAXN];   // 羊皮纸内容
char T[MAXN];             // 目标串
long long dp[MAXN];       // dp[i]表示匹配了T的前i个字符的方案数
int cnt[26];              // cnt[c]表示当前列字符c的出现次数

int main() {
    cin >> N >> L;  // 读入羊皮纸数量和长度
    
    for (int i = 0; i < N; i++) {  // 读入每卷羊皮纸
        cin >> paper[i];
    }
    cin >> T;  // 读入目标串
    
    int lenT = strlen(T);  // 目标串长度
    
    dp[0] = 1;  // 边界：未匹配任何字符，方案数为1
    
    for (int k = 0; k < L; k++) {  // 按列从左到右遍历
        memset(cnt, 0, sizeof(cnt));  // 清空计数数组
        
        for (int i = 0; i < N; i++) {  // 统计第k列每个字符的出现次数
            cnt[paper[i][k] - 'a']++;
        }
        
        for (int i = lenT; i >= 1; i--) {  // 倒序枚举，避免同一列重复使用
            int c = T[i - 1] - 'a';  // T的第i个字符（下标i-1）
            if (cnt[c] > 0) {  // 如果当前列有这个字符
                dp[i] = (dp[i] + dp[i - 1] * cnt[c]) % MOD;  // 状态转移
            }
        }
    }
    
    cout << dp[lenT] << endl;  // 输出答案
    return 0;
}