解题思路

小明的操作规则是“每次把串首的三个字符替换成一个字符”，长度每次减少 2。若初始长度为 $n$（奇数），替到只剩 1 个字符总共需要 $K=\frac{n-1}{2}$ 次操作。

正向思考较难计数，我们改为“反向展开”——从最终字符 $x$ 出发，每一步把当前串首的单字符反向替换成某个三字符（即把一条规则 $U\to V$ 反过来用：把首字母 $V$ 展开为 $U$），这样每一步长度增加 2，正好做 $K$ 次即可得到所有可能的原串。

关键观察（保证不会重复计数）：

• 设反向第 $1$ 步选了三元组 $T_1$ 且 $T_1\to x$；第 $2$ 步选 $T_2$ 且 $T_2\to T_1[0]$；…；第 $K$ 步选 $T_K$ 且 $T_K\to T_{K-1}[0]$。
• 最终长度为 $n$ 的字符串由这些三元组按固定方式拼出：位置 $0..2$ 来自 $T_K[0..2]$，位置 $3..4$ 来自 $T_{K-1}[1..2]$，位置 $5..6$ 来自 $T_{K-2}[1..2]$，以此类推直到 $T_1[1..2]$。
• 因此，“三元组序列 $(T_1,\dots,T_K)$”与“最终原串”是一一对应的，不会出现不同序列得到同一原串的情况。于是我们只需计数满足链式条件的三元组序列数量即可。

将规则看作结点（用 $U\to V$ 表示）。若两个规则 $A:U_A\to V_A$、$B:U_B\to V_B$ 满足 $V_B = U_A[0]$，则可从 $A$ 过渡到 $B$（反向下一步展开要选 $B$）。于是问题化为：

• 初始可选集合：所有 $V = x$ 的规则（这是 $T_1$）。
• 做 $K-1$ 次转移：从当前规则 $i$ 走向所有满足 $V_j = U_i[0]$ 的规则 $j$。
• 序列长度达到 $K$ 后，把所有末尾状态的方案数求和。

用简单 DP 即可：

• 若 $n=1$，无需任何展开，答案为 1（唯一原串就是 “x”）。
• 否则设 $dp^{(1)}[i]=1$ 当且仅当 $V_i=x$，再迭代 $K-1$ 轮：

实现时更自然的方向是：枚举 $i$，把 $dp^{(t)}[i]$ 加给所有满足 $V_j=U_i[0]$ 的 $j$。

算法只依赖于规则的首字母与产出字符的匹配关系，不需要构造实际字符串。

复杂度分析

• 设规则数为 $m(\le 15)$，步数 $K\le 6$。
• 每轮转移对每个规则 $i$ 把值分发给所有 $V=U_i[0]$ 的规则，最坏每轮 $O(m^2)$，总复杂度 $O(K\cdot m^2)$，在数据范围内极小。
• 额外空间 $O(m)$。

代码实现

Python

# -*- coding: utf-8 -*-
import sys

# 功能函数：根据规则与 n、x 计算可行原串数量
def count_sources(n, rules, x):
    # n==1 时无需展开，唯一原串为 x
    if n == 1:
        return 1

    K = (n - 1) // 2  # 需要的反向展开步数

    m = len(rules)
    U = [u for u, v in rules]           # 三字符 U
    V = [v for u, v in rules]           # 单字符 V
    first = [u[0] for u in U]           # 每条规则 U 的首字母

    # 建立按 V 聚类的索引：idx_by_V[c] = 所有 V==c 的规则下标列表
    idx_by_V = {}
    for i in range(m):
        c = V[i]
        idx_by_V.setdefault(c, []).append(i)

    # dp 初始化：第 1 步选择满足 V==x 的规则
    dp = [0] * m
    for i in range(m):
        if V[i] == x:
            dp[i] = 1

    # 进行 K-1 次转移
    for _ in range(K - 1):
        ndp = [0] * m
        for i in range(m):
            if dp[i] == 0:
                continue
            need = first[i]  # 下一步需要选择 V==U_i[0] 的规则
            for j in idx_by_V.get(need, []):
                ndp[j] += dp[i]
        dp = ndp

    # 累加长度为 K 的所有方案
    return sum(dp)

def main():
    data = sys.stdin.read().strip().split()
    # 输入格式：
    # 第一行：n m
    # 接下来 m 行：U V（U 长度 3，V 长度 1）
    # 最后一行：x
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    m = int(next(it))
    rules = []
    for _ in range(m):
        u = next(it)
        v = next(it)
        rules.append((u, v))
    x = next(it)
    ans = count_sources(n, rules, x)
    print(ans)

if __name__ == "__main__":
    main()

Java

// ACM 风格，类名 Main
// 思路：反向展开 + DP 计数。详见题解部分注释。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static long solve(int n, List<String> U, List<String> V) {
        if (n == 1) return 1L; // 唯一原串为 x

        int m = U.size();
        int K = (n - 1) / 2;

        char[] first = new char[m]; // U 的首字母
        for (int i = 0; i < m; i++) first[i] = U.get(i).charAt(0);

        // 建立 V -> 规则下标列表
        Map<Character, List<Integer>> idxByV = new HashMap<>();
        for (int i = 0; i < m; i++) {
            char c = V.get(i).charAt(0);
            idxByV.computeIfAbsent(c, k -> new ArrayList<>()).add(i);
        }

        // 第 1 步：选择所有 V==x 的规则
        long[] dp = new long[m];
        char x = V.get(0).charAt(0); // 占位，稍后覆盖
        // 注意：x 由输入最后一行提供，因此 solve 调用前需放好 V 的最后一项？——不，这里改为传参
        return -1L; // 这个占位返回不会被使用
    }

    public static void main(String[] args) throws Exception {
        // 读取输入：第一行 n m；接下来 m 行 U V；最后一行 x
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] nm = br.readLine().trim().split("\\s+");
        int n = Integer.parseInt(nm[0]);
        int m = Integer.parseInt(nm[1]);

        String[] U = new String[m];
        String[] V = new String[m];
        for (int i = 0; i < m; i++) {
            String line = br.readLine().trim();
            // 使用空格分隔（数据合法，不涉及特殊分隔）
            String[] parts = line.split("\\s+");
            U[i] = parts[0];
            V[i] = parts[1];
        }
        String xs = br.readLine().trim();
        char x = xs.charAt(0);

        if (n == 1) {
            System.out.println(1);
            return;
        }
        int K = (n - 1) / 2;

        // 预处理：first[i] = U[i][0]
        char[] first = new char[m];
        for (int i = 0; i < m; i++) first[i] = U[i].charAt(0);

        // 建立 V -> 规则下标列表
        Map<Character, List<Integer>> idxByV = new HashMap<>();
        for (int i = 0; i < m; i++) {
            char c = V[i].charAt(0);
            idxByV.computeIfAbsent(c, k -> new ArrayList<>()).add(i);
        }

        // dp 初始化：第 1 步选择所有 V==x 的规则
        long[] dp = new long[m];
        for (int i = 0; i < m; i++) {
            if (V[i].charAt(0) == x) dp[i] = 1L;
        }

        // 迭代 K-1 次
        for (int step = 1; step <= K - 1; step++) {
            long[] ndp = new long[m];
            for (int i = 0; i < m; i++) {
                long val = dp[i];
                if (val == 0) continue;
                char need = first[i]; // 下一步需要 V==U_i[0]
                List<Integer> lst = idxByV.get(need);
                if (lst == null) continue;
                for (int j : lst) {
                    ndp[j] += val;
                }
            }
            dp = ndp;
        }

        long ans = 0L;
        for (long v : dp) ans += v;
        System.out.println(ans);
    }
}

C++

// 思路：反向展开 + DP 计数
// 每条规则视为一个节点 U->V，转移条件为下一条规则的 V 等于当前规则 U 的首字母。
// 初始从所有 V==x 的规则出发，做 K-1 次转移，求长度为 K 的序列数量之和。
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;

    vector<string> U(m), V(m);
    for (int i = 0; i < m; ++i) {
        cin >> U[i] >> V[i]; // U 长度 3，V 长度 1
    }
    string xs; cin >> xs;
    char x = xs[0];

    if (n == 1) {
        cout << 1 << "\n";
        return 0;
    }

    int K = (n - 1) / 2;
    vector<char> first(m);
    for (int i = 0; i < m; ++i) first[i] = U[i][0];

    // 建立 V -> 下标列表
    array<vector<int>, 26> idxByV;
    for (int i = 0; i < 26; ++i) idxByV[i].clear();
    for (int i = 0; i < m; ++i) {
        int c = V[i][0] - 'a';
        idxByV[c].push_back(i);
    }

    // dp 初始化
    vector<long long> dp(m, 0), ndp(m, 0);
    for (int i = 0; i < m; ++i) if (V[i][0] == x) dp[i] = 1;

    // 迭代 K-1 次
    for (int step = 1; step <= K - 1; ++step) {
        fill(ndp.begin(), ndp.end(), 0);
        for (int i = 0; i < m; ++i) {
            if (dp[i] == 0) continue;
            int need = first[i] - 'a'; // 下一步需要 V==U_i[0]
            for (int j : idxByV[need]) {
                ndp[j] += dp[i];
            }
        }
        dp.swap(ndp);
    }

    long long ans = 0;
    for (auto v : dp) ans += v;
    cout << ans << "\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$ 为奇数。

输出描述

样例1

输入

7 4
abd e
bcd e
aba b
aba a
e

输出

2

说明