自动搬运

查看原文

来自洛谷，原作者为

	forgotmyhandle Though my wing's been bloodstained and could never rid, I will try hard to soar to the heaven I dreamed

搬运于2025-08-24 22:01:36，当前版本为作者最后更新于2023-10-04 21:22:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

传送门

分析

可以考虑 dp。先朴素地定义 $dp[i][j]$ 表示当前在结点 $i$，已经走过了 $j$ 个结点（含当前）的方案数。发现没法处理括号匹配，于是加一维 $k$ 表示当前还剩 $k$ 个前括号没有匹配。又发现没法处理前导 $0$。于是考虑再加一维表示当前的最后一位是什么状态。

发现如果要排除掉前导 $0$ 的话，只需要知道 将要转移到我的这个状态 所在结点上的 $0$ 是不是作为一个数字的开头出现的即可。于是最后一维就可以表示这个结点上的数字是否作为首位出现。当然还要考虑当前位不是数字的情况。

于是有最终的状态：$dp[i][j][k][0/1/2]$ 表示当前在 $i$ 这个结点，已经经过了 $j$ 个结点（含当前），还剩 $k$ 个前括号没有匹配。最后一维是 $1$ 代表当前结点上的数字作为首位出现，是 $0$ 代表不作为首位，是 $2$ 代表这一位根本就不是数字。

接下来考虑转移（前方有大分讨，请注意）：

对于 $dp[i][j][k][0/1/2]$，我们枚举所有与 $i$ 相邻的结点 $v$ 进行转移：

1. 若 $i$ 结点上是数字：

   1. 若 $v$ 结点上是非 $0$ 数字，则将 $dp[v][j - 1][k][0] + dp[v][j - 1][k][1]$ 加到 $dp[i][j][k][0]$，因为这时我们不关心 $v$ 上的数是否作为首位；
   2. 若 $v$ 结点上是 $0$，则将 $dp[v][j - 1][k][0]$ 加到 $dp[i][j][k][0]$，因为这时若 $v$ 上的 $0$ 作首位，后面就不能接数字；
   3. 若 $v$ 结点上是运算符或前括号，则将 $dp[v][j - 1][k][2]$ 加到 $dp[i][j][k][1]$，因为数字前面一定可以接这两者；
   4. 由于后括号之后不接数字，所以 $v$ 上是后括号时不转移。

   注意，当 $v$ 上是数字时，当前位的数字就不作为首位。当 $v$ 上不是数字，则当前位的数字就必然作为首位。

2. 若 $i$ 结点上是运算符：

   1. 若 $v$ 上为数字，则将 $dp[v][j - 1][k][0] + dp[v][j - 1][k][1]$ 加过来，因为运算符前一定可以接数字；
   2. 若 $v$ 是前括号，则当且仅当 $i$ 上为减号时可以将 $dp[v][j - 1][k][2]$ 加过来，因为这时减号作负号用，而其他运算符均没有该用法；
   3. 若 $v$ 是后括号，则将 $dp[v][j - 1][k][2]$ 加过来，因为后括号后一定可以接运算符；
   4. 由于任意两运算符不能相连，于是当 $v$ 是运算符时不转移。

3. 若 $i$ 上是前括号：

   1. 当且仅当 $v$ 上是运算符或前括号时可以将 $dp[v][j - 1][k - 1][2]$ 加过来，因为只有这两者后才可以接前括号。（没说乘号可以省就不能省（确信））

   注意，由于多了一个未匹配的前括号，所以第三维从 $k - 1$ 转移。

4. 若 $i$ 上是后括号：

   1. 若 $v$ 上是数字，则将 $dp[v][j - 1][k + 1][0] + dp[v][j - 1][k + 1][1]$ 加过来；
   2. 若 $v$ 上是后括号，则将 $dp[v][j - 1][k + 1][2]$ 加过来；
   3. 由于运算符后不能直接加后括号，括号内又不能为空，于是 $v$ 为运算符或前括号时不转移。

   注意，由于这个后括号匹配了一个前括号，所以第三维从 $k + 1$ 转移。

赋初值的时候注意，当且仅当这个结点上是数字或前括号或减号时才能有初值。

统计答案时注意，当且仅当最后一位是后括号或数字时才可以加入答案。

代码

#include <iostream>
#define int long long
using namespace std;
const int p = 1000000007;
int head[200005], nxt[400005], to[400005], ecnt;
void addE(int u, int v) { to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt; }
int n, m, K;
int dp[25][35][35][3];
// currently at point i, has passed j vertices, have k front bracket left to match
// l = (0 : this digit is not the beginning, 1 : is beginning, 2 : not a digit)
bool issym(char x) { return (x == '+' || x == '-' || x == '*' || x == '/'); }
bool isbrc(char x) { return (x == '(' || x == ')'); }
inline void add(int& x, int y) { x = (x + y) % p; }
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> K;
    string str;
    cin >> str;
    str = ' ' + str;
    for (int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        addE(u, v);
        addE(v, u);
    }
    for (int i = 1; i <= n; i++) {
        if (isdigit(str[i])) 
            dp[i][1][0][1] = 1;
        else if (str[i] == '(') 
            dp[i][1][1][2] = 1;
        else if (str[i] == '-') 
            dp[i][1][0][2] = 1;
    }
    for (int j = 2; j <= K; j++) {
        for (int i = 1; i <= n; i++) {
            for (int k = (str[i] == '('); k <= K; k++) {
                for (int l = head[i]; l; l = nxt[l]) {
                    int v = to[l];    
                    if (isdigit(str[i])) {
                        if (isdigit(str[v])) 
                            add(dp[i][j][k][0], dp[v][j - 1][k][0] + (str[v] == '0' ? 0 : dp[v][j - 1][k][1]));
                        else if (issym(str[v]) || str[v] == '(') 
                            add(dp[i][j][k][1], dp[v][j - 1][k][2]);
                    } else if (issym(str[i])) {
                        if (isdigit(str[v])) 
                            add(dp[i][j][k][2], dp[v][j - 1][k][0] + dp[v][j - 1][k][1]);
                        else if (str[v] == '(') 
                            str[i] == '-' ? add(dp[i][j][k][2], dp[v][j - 1][k][2]) : void();
                        else if (str[v] == ')') 
                            add(dp[i][j][k][2], dp[v][j - 1][k][2]);
                    } else if (str[i] == '(') {
                        if (issym(str[v]) || str[v] == '(') 
                            add(dp[i][j][k][2], dp[v][j - 1][k - 1][2]);
                    } else {
                        if (isdigit(str[v])) 
                            add(dp[i][j][k][2], dp[v][j - 1][k + 1][0] + dp[v][j - 1][k + 1][1]);
                        else if (str[v] == ')') 
                            add(dp[i][j][k][2], dp[v][j - 1][k + 1][2]);
                    }
                }
                
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (isdigit(str[i])) 
            add(ans, dp[i][K][0][0] + dp[i][K][0][1]);
        else if (str[i] == ')')
            add(ans, dp[i][K][0][2]);
    }
    cout << ans;
    return 0;
}

关于什么情况下要赋初值：

这里的 dp 值的意义实际上是当前合法的方案数 加上 当前非法但到后面可能变得合法的方案数。显然只有一个减号或前括号都是可能变得合法的，于是有初值。又显然只有一个后括号或别的运算符都是永远也不可能变得合法的，于是就没有初值。

关于统计答案：

显然这里的非法情况只有两种；运算符缺第二个参数 和 前括号没匹配完。于是只要最后一位是数字或后括号，再加上只统计第三维是 $0$ 的情况就不会出现非法。