2025-2026 ICPC NERC, Kyrgyzstan Regional Contest 吉尔吉斯斯坦——G. Secret Words（区间 DP 不适合应用于计数问题？或者说你至少要想一下，不同的区间划分会不会造成同样的计数情况） · znzryb
## 题目大意
**题目描述**
给定 $n$ 个**秘密单词**组成的列表，以及一个**目标文本** $T$。
目标文本 $T$ 由小写英文字母和符号 `?` 组成。其中 `?` 是通配符，可以匹配秘密单词中的任意一个字母。
你需要求出有多少种方法，可以将整个文本 $T$ 完全拆分为列表中的单词。
每个单词可以使用任意多次。
输出方案数对 $10^9 + 7$ 取模的结果。
**输入格式**
第一行包含一个整数 $n$ ($1 \le n \le 100$)。
接下来 $n$ 行，每行一个字符串 $W_i$ ($1 \le |W_i| \le 10$)，保证所有单词互不相同。
最后一行包含一个字符串 $T$ ($1 \le |T| \le 100$)。
**样例 1**
```
7
a
b
c
d
ab
bc
cd
ab?d
```
**输出 1**
```
11
```
**样例 1 解释**
目标文本为 `ab?d`。`?` 可以匹配任意字符，即此处的 `?` 需要根据选用的单词被“填充”。
可能的拆分方式包括：
1. `[a, b, a, d]` （第三个单词为 `a`，此时 `?` 匹配 `a`）
1. `[a, b, b, d]` （`?` 匹配 `b`）
1. `[a, b, c, d]` （`?` 匹配 `c`）
1. `[a, b, d, d]` （`?` 匹配 `d`）
1. `[ab, a, d]`
1. `[ab, b, d]`
1. `[ab, c, d]`
1. `[ab, d, d]`
1. `[a, bc, d]`
1. `[a, b, cd]`
1. `[ab, cd]`
**样例 2**
```
2
a
b
??
```
**输出 2**
```
4
```
**样例 2 解释**
目标文本为 `??`。
可能的拆分方式包括：
1. `[a, a]`
1. `[a, b]`
1. `[b, a]`
1. `[b, b]`
## 思路讲解
采用线性 DP 的方式啊，采用线性 DP 的方式。
这题的陷阱就是啊，至少是我踩中的陷阱啊。就是采用了区间 DP 的方式，因为毕竟这个数据范围比较小嘛，很容易想到区间 DP 啊。不过区间 DP 它会，虽然说二叉分裂是不同的，但是划分方式是相同的，是会有这种情况的发生。
```cpp
for (int i=0;i<N;++i) {
for (int len=1;len<=10;++len) {
if (i-len+1<0) {
break;
}
// 一个 string view 啊，这个 view 就是从 i 减 len 加一开始，长度为 len 的一个 view。
string_view s_view(s.data()+i-len+1,len);
ll valid_num=0;
// 这个循环就是计算 valid num 的数量。说白了就是长度为 len 的合法单一划分数量。
for (auto &ls:len_words_mtx[len]) {
bool ok=true;
for (int j=0;j<SZ(ls);++j) {
if (ls[j]==s_view[j] || s_view[j]=='?') {
}else {
ok=false;
}
}
if (ok) {
valid_num++;
}
}
// 从 i - len 处转移，一共有 valid num 种转移方法，所以说是乘法原理。
// 注意 i - len 为小于零的时候是空，也是 1 种合法的方案。
dp[i]+=(i-len<0?1:dp[i-len])*valid_num;
dp[i]%=mod;
}
}
```
## AC代码
AC
[https://codeforces.com/gym/106169/submission/363004216](https://codeforces.com/gym/106169/submission/363004216)
::: 源代码
```cpp
/**
* Problem: G. Secret Words
* Contest: 2025
* Judge: Codeforces
* URL: https://codeforces.com/gym/106169/problem/G
* Created: 2026-02-15 15:41:59
* Author: Gospel_rock
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define debug3d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " [\n"; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
{ \
cerr << " ["; \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k]; \
cerr << "]\n"; \
} \
cerr << " ]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
/*
*
*/
void Solve() {
ll num_words;
cin >> num_words;
vector<string> secret_word(num_words+2);
// set<string> words_st;
vector<vector<string>> len_words_mtx(15);
for (int i=1;i<=num_words;++i) {
cin>>secret_word[i];
// words_st.insert(secret_word[i]);
len_words_mtx[SZ(secret_word[i])].push_back(secret_word[i]);
}
string s;
cin>>s;
ll N=SZ(s);
vector<ll> dp(N+2);
for (int i=0;i<N;++i) {
for (int len=1;len<=10;++len) {
if (i-len+1<0) {
break;
}
string_view s_view(s.data()+i-len+1,len);
ll valid_num=0;
for (auto &ls:len_words_mtx[len]) {
bool ok=true;
for (int j=0;j<SZ(ls);++j) {
if (ls[j]==s_view[j] || s_view[j]=='?') {
}else {
ok=false;
}
}
if (ok) {
valid_num++;
}
}
dp[i]+=(i-len<0?1:dp[i-len])*valid_num;
dp[i]%=mod;
}
}
cout<<dp[N-1]<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
// cin >> lT;
// for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
AC
https://codeforces.com/gym/106169/submission/363004216
*/
```
:::
## 心路历程（WA，TLE，MLE……）
::: 会算重复的区间 dp 做法
为什么区间 DP 会算重复呢？是这样子的，虽然我们采用了不同的二叉划分，虽然我们采用了不同的二叉划分，但是**在采用不同二叉划分的段里面**呢，实际上**有划分是完全相同的**。的东西的。
因此我们必须得**要采用线性 DP 做法**。
```cpp
auto dfs=[&](auto && self,ll l,ll r) -> void {
if (vis[l][r]) {
return;
}
vis[l][r]=1;
ll len=r-l+1;
if (!len_words_mtx[len].empty()) {
for (auto &ls:len_words_mtx[len]) {
bool ok=true;
for (int i=0;i<ls.size();++i) {
if (s[l+i]==ls[i] || s[l+i]=='?') {
}else {
ok=false;
break;
}
}
if (ok) {
dp[l][r]++;
}
}
}
for (ll sp=l;sp<r;++sp) {
self(self,l,sp);
self(self,sp+1,r);
dp[l][r]+=dp[l][sp]*dp[sp+1][r];
dp[l][r]%=mod;
}
};
```
```cpp
/**
* Problem: G. Secret Words
* Contest: 2025
* Judge: Codeforces
* URL: https://codeforces.com/gym/106169/problem/G
* Created: 2026-02-15 13:44:16
* Author: Gospel_rock
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define debug3d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " [\n"; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
{ \
cerr << " ["; \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k]; \
cerr << "]\n"; \
} \
cerr << " ]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
/*
*
*/
void Solve() {
ll N;
cin >> N;
vector<string> secret_word(N+2);
// set<string> words_st;
vector<vector<string>> len_words_mtx(15);
for (int i=1;i<=N;++i) {
cin>>secret_word[i];
// words_st.insert(secret_word[i]);
len_words_mtx[SZ(secret_word[i])].push_back(secret_word[i]);
}
string s;
cin>>s;
vector<vector<ll>> dp(SZ(s)+2,vector<ll>(SZ(s)+2));
vector<vector<char>> vis(SZ(s)+2,vector<char>(SZ(s)+2));
auto dfs=[&](auto && self,ll l,ll r) -> void {
if (vis[l][r]) {
return;
}
vis[l][r]=1;
ll len=r-l+1;
if (!len_words_mtx[len].empty()) {
for (auto &ls:len_words_mtx[len]) {
bool ok=true;
for (int i=0;i<ls.size();++i) {
if (s[l+i]==ls[i] || s[l+i]=='?') {
}else {
ok=false;
break;
}
}
if (ok) {
dp[l][r]++;
}
}
}
for (ll sp=l;sp<r;++sp) {
self(self,l,sp);
self(self,sp+1,r);
dp[l][r]+=dp[l][sp]*dp[sp+1][r];
dp[l][r]%=mod;
}
};
dfs(dfs,0,SZ(s)-1);
cout<<dp[0][SZ(s)-1]<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
// cin >> lT;
// for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
*/
```
:::