题目分析

给定一个 $N$ 个节点的无向图，每个节点有一个符号（数字、运算符或括号）。需要统计所有长度为 $K$ 的路径，使得路径上的符号序列构成合法的算术表达式。

关键约束：

• 数字不能有前导零
• 负号只有在表达式开头或左括号后有效
• 括号必须正确匹配
• 运算符使用符合语法规则

解题思路

核心思想

使用动态规划结合文法验证：

1. 定义DP状态记录路径长度、当前位置、括号平衡和前导零状态
2. 通过状态转移模拟算术表达式的文法规则
3. 在图上进行路径枚举时实时验证表达式合法性

关键技术

• 状态设计：四维DP跟踪路径进度和语法状态
• 符号分类：将字符按语法角色分类处理
• 文法规则编码：在状态转移中嵌入表达式语法约束

算法步骤

1. 符号分类预处理
2. DP状态初始化（单字符路径）
3. 状态转移：根据当前和下一符号类型更新状态
4. 结果统计：收集所有合法的完整表达式路径

完整代码

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

const int p = 1e9 + 7;

int read() {
    char ch = getchar();
    int num = 0, sign = 1;
    while (ch < '0' || ch > '9') {
        if (ch == '-') sign = -sign;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        num = (num << 3) + (num << 1) + (ch ^ 48);
        ch = getchar();
    }
    return sign * num;
}

int n, m, k;
string s;
int f[33][22][33][2];  // f[步数][节点][未匹配左括号数][是否以0开头]
vector<int> e[22];     // 图的邻接表

// 符号类型分类
int Type(char c) {
    if (c == '(') return 0;        // 左括号
    else if (c == ')') return 1;   // 右括号
    else if (c == '-') return 2;   // 减号（可作负号）
    else if (c == '+' || c == '*' || c == '/') return 3; // 其他运算符
    else if (c == '0') return 4;   // 数字0
    else return 5;                 // 数字1-9
}

signed main() {
    n = read(), m = read(), k = read();
    cin >> s;
    s = " " + s;  // 调整为1-indexed
    
    // 建图
    for (int i = 1, u, v; i <= m; i++) {
        u = read(), v = read();
        e[u].push_back(v);
        e[v].push_back(u);
    }
    
    // DP初始化：单字符路径
    for (int i = 1; i <= n; i++) {
        int t = Type(s[i]);
        // 合法的起始字符：左括号、数字、负号（不能是右括号或其他运算符）
        if (t != 1 && t != 3) {
            int bracket_add = (s[i] == '(') ? 1 : 0;
            int is_zero = (s[i] == '0') ? 1 : 0;
            f[1][i][1 + bracket_add][is_zero] = 1;
        }
    }
    
    // DP状态转移
    for (int dep = 1; dep < k; dep++) {
        for (int i = 1; i <= n; i++) {
            for (int cnt = 1; cnt <= dep + 1; cnt++) {
                for (int isz = 0; isz <= 1; isz++) {
                    int current = f[dep][i][cnt][isz];
                    if (!current) continue;
                    
                    int current_type = Type(s[i]);
                    
                    // 遍历所有邻接节点
                    for (int j : e[i]) {
                        int next_type = Type(s[j]);
                        
                        // 根据当前符号类型进行状态转移
                        if (current_type == 0) {  // 当前是 '('
                            if (next_type == 0) {  // '(' 后接 '('
                                f[dep + 1][j][cnt + 1][0] = (f[dep + 1][j][cnt + 1][0] + current) % p;
                            } else if (next_type == 2) {  // '(' 后接 '-'
                                f[dep + 1][j][cnt][0] = (f[dep + 1][j][cnt][0] + current) % p;
                            } else if (next_type == 4) {  // '(' 后接 '0'
                                f[dep + 1][j][cnt][1] = (f[dep + 1][j][cnt][1] + current) % p;
                            } else if (next_type == 5) {  // '(' 后接 '1'-'9'
                                f[dep + 1][j][cnt][0] = (f[dep + 1][j][cnt][0] + current) % p;
                            }
                            // 其他情况不合法：')', 其他运算符
                        } 
                        else if (current_type == 1) {  // 当前是 ')'
                            if (next_type == 1) {  // ')' 后接 ')'
                                if (cnt > 1) {
                                    f[dep + 1][j][cnt - 1][0] = (f[dep + 1][j][cnt - 1][0] + current) % p;
                                }
                            } else if (next_type == 2 || next_type == 3) {  // ')' 后接运算符
                                f[dep + 1][j][cnt][0] = (f[dep + 1][j][cnt][0] + current) % p;
                            }
                            // 其他情况不合法：'(', 数字
                        } 
                        else if (current_type == 2) {  // 当前是 '-'
                            if (next_type == 0) {  // '-' 后接 '('
                                f[dep + 1][j][cnt + 1][0] = (f[dep + 1][j][cnt + 1][0] + current) % p;
                            } else if (next_type == 4) {  // '-' 后接 '0'
                                f[dep + 1][j][cnt][1] = (f[dep + 1][j][cnt][1] + current) % p;
                            } else if (next_type == 5) {  // '-' 后接 '1'-'9'
                                f[dep + 1][j][cnt][0] = (f[dep + 1][j][cnt][0] + current) % p;
                            }
                            // 其他情况不合法：')', 运算符
                        } 
                        else if (current_type == 3) {  // 当前是其他运算符
                            if (next_type == 0) {  // 运算符后接 '('
                                f[dep + 1][j][cnt + 1][0] = (f[dep + 1][j][cnt + 1][0] + current) % p;
                            } else if (next_type == 4) {  // 运算符后接 '0'
                                f[dep + 1][j][cnt][1] = (f[dep + 1][j][cnt][1] + current) % p;
                            } else if (next_type == 5) {  // 运算符后接 '1'-'9'
                                f[dep + 1][j][cnt][0] = (f[dep + 1][j][cnt][0] + current) % p;
                            }
                            // 其他情况不合法：')', 运算符
                        } 
                        else if (current_type == 4) {  // 当前是 '0'
                            if (next_type == 1) {  // '0' 后接 ')'
                                if (cnt > 1) {
                                    f[dep + 1][j][cnt - 1][0] = (f[dep + 1][j][cnt - 1][0] + current) % p;
                                }
                            } else if (next_type == 2 || next_type == 3) {  // '0' 后接运算符
                                f[dep + 1][j][cnt][0] = (f[dep + 1][j][cnt][0] + current) % p;
                            } else if (next_type == 4 || next_type == 5) {  // '0' 后接数字
                                if (isz == 0) {  // 只有当前不是以0开头时才允许
                                    f[dep + 1][j][cnt][0] = (f[dep + 1][j][cnt][0] + current) % p;
                                }
                            }
                            // 其他情况不合法：'('
                        } 
                        else if (current_type == 5) {  // 当前是 '1'-'9'
                            if (next_type == 1) {  // 数字后接 ')'
                                if (cnt > 1) {
                                    f[dep + 1][j][cnt - 1][0] = (f[dep + 1][j][cnt - 1][0] + current) % p;
                                }
                            } else if (next_type == 2 || next_type == 3) {  // 数字后接运算符
                                f[dep + 1][j][cnt][0] = (f[dep + 1][j][cnt][0] + current) % p;
                            } else if (next_type == 4 || next_type == 5) {  // 数字后接数字
                                f[dep + 1][j][cnt][0] = (f[dep + 1][j][cnt][0] + current) % p;
                            }
                            // 其他情况不合法：'('
                        }
                    }
                }
            }
        }
    }
    
    // 统计结果：所有合法的完整表达式
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int isz = 0; isz <= 1; isz++) {
            int t = Type(s[i]);
            // 合法结尾：数字、右括号（不能是左括号或运算符）
            if (t != 0 && t != 2 && t != 3) {
                // 括号必须完全匹配（cnt == 1）
                ans = (ans + f[k][i][1][isz]) % p;
            }
        }
    }
    
    cout << ans << endl;
    return 0;
}

代码说明

关键数据结构

• f[dep][i][cnt][isz]：DP状态数组

  • dep：已走步数（1到k）
  • i：当前节点编号
  • cnt：未匹配的左括号数量
  • isz：当前数字是否以0开头（防止前导零）

• e[i]：图的邻接表

• Type(c)：符号分类函数

文法规则实现

1. 前导零处理：

   • 数字0后只能接运算符、右括号或其他非数字字符
   • 通过isz标志位跟踪

2. 括号匹配：

   • 遇到'('时cnt加1
   • 遇到')'时cnt减1（需cnt > 1）
   • 最终必须cnt == 1（完全匹配）

3. 运算符规则：

   • 负号只能在开头或'('后
   • 运算符后必须接数字或'('

算法流程

1. 初始化：所有合法的单字符表达式
2. 状态转移：根据当前和下一字符类型，应用文法规则
3. 结果收集：所有括号平衡且语法正确的k长度路径

复杂度分析

• 时间复杂度：$O(K^2 \cdot N \cdot M)$
  • $K \leq 30$，$N \leq 20$，$M \leq N^2$
  • 总操作数约 $30^2 \times 20 \times 400 = 7.2 \times 10^6$
• 空间复杂度：$O(K^2 \cdot N)$