解题思路

题意简化一下：

• 有很多规则：U -> V，其中 U 是长度为 3 的字符串，V 是长度为 1 的字符。

• 每一次操作：只能把当前串“开头的 3 个字符”替换成一个字符。 也就是： 若当前串为 S = U + suffix，并且有规则 U -> V，那么可以把 S 变成 V + suffix。

• 已知：

  • 最终替换得到的单个字符是 x
  • 原串长度为 n（奇数）

• 问：长度为 n 的原串 S 一共有多少种不同的可能？

反向构造 + 按长度分层 BFS

正向过程： 从一个长度为 n 的串，不断用“首 3 个字符”替换为 1 个字符，长度每次减 2，最后得到长度为 1 的字符 x。

我们不知道原串，只知道最后是 x，因此可以考虑反向构造：

• 正向： 若有规则 U -> V，且当前串形如 U + suffix，则变成 V + suffix。
• 反向： 若当前串形如 V + suffix，并且有规则 U -> V，那么它可能来自 U + suffix。 即：把首字符 V 反向扩展成 3 个字符 U。

于是反向操作是：

当前串 s = c + tail
若存在规则 u -> c
则上一层的可能：t = u + tail

每做一次反向操作，长度会从 L 变成 L + 2。 因为我们最终要得到长度为 n 的串，而且 n 为奇数，所以从长度 1 开始，每次加 2： 1, 3, 5, ..., n，正好能到达。

使用“分层 BFS”（按长度推）

我们可以把“长度”当成 BFS 的层数来做：

• 定义 dp[len]：所有长度为 len 的、可以在若干步正向变成 x 的字符串集合。

• 初始层：

  • dp[1] = { x }

• 对于每个奇数长度 len，向长度 len + 2 推：

  • 遍历 dp[len] 中的所有串 s：

    • 记 s[0] = c，s[1:] = tail

    • 要找所有规则 u -> c

    • 对每个这样的 u，构造新串：

      t = u + tail
      

    • 把所有得到的 t 放入 dp[len + 2] 的集合中（用 set 自动去重）。

• 最后答案就是：dp[n] 中不同字符串的个数。

规则的存储方式

为了高效找到“哪些 u 能够产生某个字符 c”，我们预处理：

toPrefix[c] = [ u1, u2, ... ]  # 所有满足 u -> c 的 u

这样当我们看到某个串以 c 开头时，就能快速拿到所有可能的 u，进行扩展。

与普通 BFS 的关系

• 这是一个“按长度分层”的 BFS，本质上仍然是广度优先搜索，只是我们不是用队列一层层出队，而是用 dp[len] 这种按层存储的方式来推进。
• 每一层只依赖上一层，且长度严格递增，不会出现环，也不需要额外的全局 visited；字符串只会在属于自己长度的层里去重。

复杂度分析

设不同长度的中间字符串总数为 K，规则数为 m，最大长度为 n ≤ 13。

• 每一层 len 我们遍历 dp[len] 里的所有串；
• 对每个串，只看首字符，找到对应的规则列表，规则总量不超过 m；
• 每条规则只会被用于构造新串一次（对不同的 s）。

整体复杂度大致为：

• 时间复杂度：O(K * m)，在本题数据范围内非常安全。
• 空间复杂度：O(K)，只保存每层的集合。

代码实现

Python

import sys
from collections import defaultdict

# 使用分层 BFS（按长度）反向构造所有可能的原串
def solve():
    input = sys.stdin.readline
    n, m = map(int, input().split())

    # 反向映射：对于每个字符 v，存储所有可以 v = (u -> v) 的 u
    to_prefix = defaultdict(list)
    for _ in range(m):
        u, v = input().split()
        to_prefix[v].append(u)

    x = input().strip()  # 最终得到的字符

    # dp[len] 表示长度为 len 的所有可能字符串集合
    dp = [set() for _ in range(n + 1)]
    dp[1].add(x)  # 初始长度 1，只能是 x

    # 长度从 1 开始，每次加 2，一直到 n
    for length in range(1, n, 2):
        if not dp[length]:
            continue  # 这一层没有任何字符串，跳过
        for s in dp[length]:
            # 串首字符
            c = s[0]
            # 没有任何规则能产生这个字符，就无法反向扩展
            if c not in to_prefix:
                continue
            tail = s[1:]  # 除去首字符后的部分
            # 对所有 u -> c 的规则进行反向扩展
            for u in to_prefix[c]:
                # 把首字符 c 反向展开为 u
                t = u + tail
                # 新长度一定是 length + 2，这里加判断方便理解，也保证不超过 n
                if len(t) <= n:
                    dp[length + 2].add(t)

    # 答案是长度为 n 的所有不同字符串数量
    print(len(dp[n]))


if __name__ == "__main__":
    solve()

Java

import java.util.*;

// 使用按长度分层的 BFS，逐层反向扩展
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();  // 原串长度
        int m = sc.nextInt();  // 规则数量

        // 反向映射：字符 v -> 能产生 v 的所有 u
        Map<String, List<String>> toPrefix = new HashMap<>();
        for (int i = 0; i < m; i++) {
            String u = sc.next();
            String v = sc.next();
            if (!toPrefix.containsKey(v)) {
                toPrefix.put(v, new ArrayList<String>());
            }
            toPrefix.get(v).add(u);
        }

        String x = sc.next();  // 最终字符

        // dp[len] 表示长度为 len 的所有可能字符串集合
        @SuppressWarnings("unchecked")
        HashSet<String>[] dp = new HashSet[n + 1];
        for (int i = 0; i <= n; i++) {
            dp[i] = new HashSet<>();
        }
        dp[1].add(x);  // 初始只有长度为 1 的 x

        // 从长度 1 开始，每次扩展到长度 len + 2
        for (int len = 1; len < n; len += 2) {
            if (dp[len].isEmpty()) continue;
            for (String s : dp[len]) {
                // 串首字符
                String c = s.substring(0, 1);
                if (!toPrefix.containsKey(c)) continue;
                String tail = s.substring(1);  // 去掉首字符后的部分
                List<String> list = toPrefix.get(c);
                // 对所有 u -> c 的规则做反向扩展
                for (String u : list) {
                    String t = u + tail;
                    if (t.length() <= n) {
                        dp[len + 2].add(t);
                    }
                }
            }
        }

        // 最后一层长度为 n 的集合大小即为答案
        System.out.println(dp[n].size());
    }
}

C++

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

// 使用分层 BFS 按长度反向构造
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    // 反向映射：字符 v -> 所有能产生 v 的 u
    unordered_map<char, vector<string>> toPrefix;
    for (int i = 0; i < m; i++) {
        string u, v;
        cin >> u >> v;
        char ch = v[0];   // v 是一个字符
        toPrefix[ch].push_back(u);
    }

    string x;
    cin >> x;  // 最终得到的字符（长度为 1）

    // dp[len]：长度为 len 的所有可能字符串集合
    vector<unordered_set<string>> dp(n + 1);
    dp[1].insert(x);

    // 从长度 1 开始，每次扩展到 len + 2
    for (int len = 1; len < n; len += 2) {
        if (dp[len].empty()) continue;
        for (const string &s : dp[len]) {
            char c = s[0];           // 首字符
            auto it = toPrefix.find(c);
            if (it == toPrefix.end()) continue;
            string tail = s.substr(1);  // 后缀部分
            // 对所有 u -> c 的规则进行反向扩展
            for (const string &u : it->second) {
                string t = u + tail;
                if ((int)t.size() <= n) {
                    dp[len + 2].insert(t);
                }
            }
        }
    }

    cout << dp[n].size() << "\n";
    return 0;
}

题目内容

小明热表于研究字符替换。他拥有一张字符替换表，表上的每一条替换规则形如:将字符串串首的三个连续字符用某个单字符替换。一张替换表示例如下:

$\begin{array}{|c|c|c|} \hline \text { 规则编号 } & \text { 替换前 } & \text { 替换后 } \\ \hline 1 & a b d & e \\ \hline 2 & b c d & e \\ \hline 3 & a b a & b \\ \hline 4 & a b a & a \\ \hline \end{array}$

利用这张替换表，我们就可以对一个字符串进行字符替换了。例如，对于字符串 $ababacd$ 就可以通过如下操作替换成 $e$ 。

一天，小明利用他新研究出的字符替换表将一个长为 $n$ 的字符串 $S$ 替换成了一个单字符 $x$ 在那之后，他睡了一觉，等到醒来的时候， $S$ 竟然遗失了。

小明想知道，在已知字符替换表和单字符 $x$ 的情况下，$S$ 有多少种不同的可能?

输入描述

第一行两个正整数 $n,m$ ,分别表示 $S$ 的长度和字符替换表中的规则数量。保证 $n$ 为奇数。

接下来 $m$ 行，每一行两个字符串 $U,V$ ,表示一条替换规则($U$ 替换成 $V$ ).保证 $U$ 长度为 $3$ ，$V$ 长度为 $1$ 。保证不会有完全相同的两条替换规则(即不存在 $i,j(i≠j)$ 同时满足 $U_i=U_j$ 和 $V_i=V_j$).

接下来一行一个字符 $x$ ,表示经过替换最终得到的单字符。

对于本题中出现的所有字符/字符串(包括 $U，V,x$)，保证它们仅由小写英文字母组成。

$1≤n≤ 13,1 ≤ m ≤ 15$,且 $n$ 为奇数。

输出描述

输出行一个整数，表示替换前的 $S$ 有多少种不同的可能。

样例1

输入

5 5
acd b
acf b
bcc c
bdd e
ccc e
e

输出

3

说明

三种可能的 $S$ 分别为 $add, acfdd$ , 和 $bccc$ 可以证明没有其它满足条件的 $S$

样例2

输入

9 4
abc d
def g
ghi j
jkl m
m

输出

1

说明

唯一可能的 $S$ 是 $abcefhiki$.