2025-2026 ICPC NERC, Kyrgyzstan Regional Contest 吉尔吉斯斯坦——G. Secret Words（区间 DP 不适合应用于计数问题？或者说你至少要想一下，不同的区间划分会不会造成同样的计数情况）

题目大意

题目描述

给定 $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

样例 1 解释

目标文本为 ab?d。? 可以匹配任意字符，即此处的 ? 需要根据选用的单词被“填充”。
可能的拆分方式包括：

[a, b, a, d] （第三个单词为 a，此时 ? 匹配 a）
[a, b, b, d] （? 匹配 b）
[a, b, c, d] （? 匹配 c）
[a, b, d, d] （? 匹配 d）
[ab, a, d]
[ab, b, d]
[ab, c, d]
[ab, d, d]
[a, bc, d]
[a, b, cd]
[ab, cd]

样例 2

2
a
b
??

输出 2

样例 2 解释

目标文本为 ??。
可能的拆分方式包括：

[a, a]
[a, b]
[b, a]
[b, b]

思路讲解

采用线性 DP 的方式啊，采用线性 DP 的方式。

这题的陷阱就是啊，至少是我踩中的陷阱啊。就是采用了区间 DP 的方式，因为毕竟这个数据范围比较小嘛，很容易想到区间 DP 啊。不过区间 DP 它会，虽然说二叉分裂是不同的，但是划分方式是相同的，是会有这种情况的发生。

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代码

https://codeforces.com/gym/106169/submission/363004216

源代码

/**
 * 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 做法。

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;
    }
};

/**
 * 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;
}

/*

*/