COCI20102011 Contest#Final D (dp)

我们将一个操作序列看做由左右括号，空格构成的字符串，则序列大致长这个样子

$\text{_ ( ( ) _ ( ) ) ( _ ( ( ) ) ( }$

很显然，一个失配的左括号只能在最外层出现，而空格可以出现在任意位置

dp一个括号序列让人想到区间dp，但是这个题目的区间实际只需要用长度就可以描述

令$dp[t][l][r][f1][f2]$表示用$t$的时间从$l$走到$r$，$f1$表示是不是最外层括号，$f2$表示当前$dp$是否受到单纯括号序列的限制

其中，引入的单纯括号序列是为了防止出现重复转移，其意思就是这个括号序列两端必须是一对匹配的左右括号，而中间随意

转移大致如下:

1.那么对于非单纯的括号序列，可以在序列插入空格或者失配的左括号(需要满足$f1$)，从$dp[t-1]$转移过来

2.对于任何的括号序列，都可以在两端找到匹配的的左右括号，从$dp[t-2]$转移过来，且完成匹配后$f1$应为$0$

3.且一个非单纯的括号序列是可以分割的，为了不重复，强制分割的左序列是单纯的即可

实际会发现，一个单纯的括号序列可以认为一定不是最外层括号，即$f2$为真时，$f1$一定为假，所以可以压缩为三种状态

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define reg register
#define rep(i,a,b) for(reg int i=a;i<=b;++i)
#define drep(i,a,b) for(reg int i=a;i>=b;--i)
char IO;
int rd(){
    int s=0;
    while(!isdigit(IO=getchar()));
    do s=(s<<1)+(s<<3)+(IO^'0');
    while(isdigit(IO=getchar()));
    return s;
}

const int N=51,P=10007;

int n,m,T;
int E[N][N];
int dp[N][N][N][2][2];

int main(){
    n=rd(),m=rd(),T=rd();
    memset(E,-63,sizeof E);
    rep(i,1,m) {
        int u=rd(),v=rd(),c=IO==' '?getchar():IO;
        if(c>='A' && c<='Z') E[u][v]=c-'A'+1;
        else if(c>='a' && c<='z') E[u][v]='a'-c-1;
        else E[u][v]=0;
    }
    rep(i,1,n) rep(j,0,1) dp[0][i][i][j][0]=1;
    rep(k,1,T){
        rep(l,1,n) rep(r,(k<T?1:n),n) rep(fl,0,1) rep(fl2,0,1) {
            ll res=0;
            if(!fl2) {
                rep(i,2,k-1) rep(j,1,n) res+=dp[i][l][j][0][1]*dp[k-i][j][r][fl][0];
                rep(i,1,n) if(E[l][i]>=0 && (!E[l][i] || fl)) res+=dp[k-1][i][r][fl][fl2];
            }
            if(k>1) rep(i,1,n)
                if(E[l][i]>0) rep(j,1,n) 
                    if(E[j][r]+E[l][i]==0) res+=dp[k-2][i][j][0][0];
            dp[k][l][r][fl][fl2]=res%P;
        }
    }
    int ans=0;
    rep(i,1,T) ans+=dp[i][1][n][1][0];
    printf("%d\n",ans%P);
}