题意：给定一个只由左右括号组成的字符串s，问长度为2*n的包含它的合法括号序列方案数，答案对1e9+7取模
1≤n≤100，1≤|s|≤200
思路：暴力预处理出s的每个前缀[0..i]后加左右括号分别能与原序列最长匹配到的位置，这一步也可以用KMP
设dp[i][j][k][l]为当前到第i位，未匹配的左括号数为j，当前最长能匹配到s的前k位，是否存在过全匹配s的方案数
有两种转移，第i+1位填左括号或者右括号
答案即为 simga dp[n<<1][0][i][1] (i=0..len(s))
学习用C++的string……
用C++的话DP的式子可以写的灵活一点，毕竟不是P，多用表达式
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 #define N 210 7 #define oo 10000000 8 #define MOD 1000000007 9 10 int dp[N][N][N][2],len[N][2],n,m; 11 string a; 12 13 void Add(int &a,int b) 14 { 15 a+=b; 16 if(a>=MOD) a-=MOD; 17 } 18 19 int calc(string b) 20 { 21 int len=b.size(); 22 for(int i=len;i>0;i--) 23 if(a.substr(0,i)==b.substr(len-i,i)) return i; 24 return 0; 25 } 26 27 int main() 28 { 29 int n; 30 scanf("%d",&n); 31 cin>>a; 32 int m=a.size(); 33 if(a[0]=='(') len[0][0]=1; 34 else len[0][1]=1; 35 string t; 36 for(int i=0;i<=m-1;i++) 37 { 38 t+=a[i]; 39 t+='('; 40 len[i+1][0]=calc(t); 41 t.pop_back(); 42 t+=')'; 43 len[i+1][1]=calc(t); 44 t.pop_back(); 45 } 46 dp[0][0][0][0]=1; 47 for(int i=0;i<=2*n-1;i++) 48 for(int j=0;j<=n;j++) 49 for(int k=0;k<=m;k++) 50 for(int l=0;l<=1;l++) 51 { 52 if(j+1<=n) Add(dp[i+1][j+1][len[k][0]][l|len[k][0]==m],dp[i][j][k][l]); 53 if(j) Add(dp[i+1][j-1][len[k][1]][l|len[k][1]==m],dp[i][j][k][l]); 54 } 55 int ans=0; 56 for(int i=0;i<=m;i++) Add(ans,dp[n<<1][0][i][1]); 57 printf("%d ",ans); 58 return 0; 59 } 60