P4580 [bjoi2014] path

A simple , No one wrote a solution , I come ,（ I don't know how to write a question , Great gods, do me a favor ...）

Title Description

In a N An undirected graph of nodes （ No self ring 、 Heavy edge ） On , Each point has a symbol , It could be numbers , It could also be a plus sign 、 minus sign 、 Multiplication sign 、 devide 、 parentheses . You have to count on this chart , How many kinds of walking just happen K A method of nodes , Make passing symbols string together to get an arithmetic expression . The start and end points of the path can be selected at will .

The so-called arithmetic expression , Is a series of numbers connected by operators . Parentheses can be inserted into expressions to indicate the order of operations .

Be careful , You have to deal with all kinds of situations , For example, the number cannot have redundant leading 0, The minus sign can only be used as a minus sign if there is no operator or number in front of it , Brackets can be added at will （ But no empty parentheses ）,0 You can do divisor （ We only consider grammar, not semantics ）, A plus sign cannot be a plus sign .

for example , The following is a valid expression ：

-0/0
((0)+(((2*3+4)+(-5)+7))+(-(2*3)*6))

The following is not a valid expression ：

001+0
1+2(2)
3+-3
--1
+1
()

Input format

The first row has three integers N,M,K, Number of points , The number of edges and the number of nodes .

The second line is a string , A symbol for each point .

Next M That's ok , Two numbers per line , Represents the number of two points connected by an edge .

1≤N≤20,0≤M≤N×(N-1)/2,0≤K≤30

Output format

Output a line of integers , Indicates the number of methods taken . This number may be large , You just need to output it 1000000007 The remainder of .

I/o sample

Input #1 Copy

6 10 3
)(1*+0
1 2
1 3
1 4
2 3
3 4
2 5
3 5
3 6
4 6
5 6

Output #1 Copy

10

explain / Tips

Altogether 10 Paths , The constituent expressions are 101, (1), 1+1, 1+0, 1*1, 1*0, 0+0, 0+1, 0*0, 0*1

Code up

#include <iostream>
#include <cstring>
#include <string>

using namespace std;

const int MAXN = 40;
const int MOD = 1000000007;

int N,M,K;
char s[30];

bool is_digit(char c)
{
    return c >= '0' && c <= '9';
}

bool is_operator(char c)
{
    return c == '+' || c == '-' || c == '*' || c == '/';
}

int g[MAXN][MAXN];
int dp[MAXN][MAXN][MAXN][2];

int dfs(int u, int k, int p, int z)
{
    if(dp[u][k][p][z] >= 0)
        return dp[u][k][p][z];
    int ret = 0;
    if(k == K){
        if((p==0) && !is_operator(s[u]))
            ret = 1;
        else 
            ret = 0;
        return dp[u][k][p][z] = ret; 
    }
    for(int v = 0; v < N; ++v){
        if(g[u][v]){
            
            if(is_digit(s[v])){
                if(is_digit(s[u]) && !z){
                    ret += dfs(v, k+1, p, 0);
                    ret %= MOD;
                }
                else if(is_operator(s[u]) || s[u] == '('){
                    ret += dfs(v, k+1, p, s[v] == '0');
                    ret %= MOD;
                }
            }
            else if(s[v] == '('){
                if(s[u] == '(' || is_operator(s[u])){
                    ret += dfs(v, k+1, p+1, 0);
                    ret %= MOD;
                }
            }
           
            else if(s[v] == ')'){
                
                if(p > 0 && (is_digit(s[u]) || s[u] == ')')){
                    ret += dfs(v, k+1, p-1, 0);
                    ret %= MOD;
                }
            }
           
            else {
                if(is_digit(s[u])){
                    ret += dfs(v, k+1, p, 0);
                    ret %= MOD;
                }
                if(s[u] == ')' || (s[u] == '(' && s[v] == '-')){
                    ret += dfs(v, k+1, p, 0);
                    ret %= MOD;
                }
            }
        }
    }
    return dp[u][k][p][z] = ret;
}

int main()
{
    
    cin >> N >> M >> K;
    cin >> s;

    memset(g,0,sizeof(g));
    memset(dp, -1, sizeof(dp));

    for(int i = 1; i <= M; ++i){
        int u,v;
        cin >> u >> v;
        u--;
        v--;
        g[u][v] = g[v][u] = 1;
    }

    int ans = 0;
    for(int u = 0; u < N; ++u){
        if(s[u] == '('){
            ans += dfs(u,1,1,0);
            ans %= MOD;
        }
        else if(s[u] == '-'){
            ans += dfs(u,1,0,0);
            ans %= MOD;
        }
        else if(is_digit(s[u])){
            ans += dfs(u,1,0,s[u]=='0');
            ans %= MOD;    
        }
    }
    cout << ans << endl;
    return 0;
}

everyone 6.1 Happy No , Happy to leave a message .

886