ShareText.Cn

搜索
最新
dp
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. char s1[2505], s2[2505];
  5. int dp[2][2505], pre[2][2505], mod = 1e9+7;
  6.  
  7. int main()
  8. {
  9.     scanf("%s%s",s1+1,s2+1);
  10.     int len1 = strlen(s1+1), len2 = strlen(s2+1), cur = 0;
  11.     dp[cur][0] = 1;
  12.     for(int i = 0; i <= len1; ++i)
  13.     {
  14.         if(i) cur ^= 1;
  15.         if(i) memset(dp[cur], 0, sizeof(dp[cur]));
  16.         for(int j = 0; j <= len2; ++j)
  17.         {
  18.             if(i == 0 && j == 0) continue;
  19.             if(j) pre[cur][j] = pre[cur][j-1] + (s2[j] == '(' ? 1 : -1);
  20.             else pre[cur][j] = pre[cur^1][j] + (s1[i] == '(' ? 1 : -1);
  21.  
  22.             if(pre[cur][j] < 0) continue;
  23.             if(i) dp[cur][j] += dp[cur^1][j];
  24.             if(j) dp[cur][j] += dp[cur][j-1];
  25.             dp[cur][j] %= mod;
  26.         }
  27.     }
  28.     if(pre[cur][len2] == 0) printf("%dn",dp[cur][len2]);
  29.     else printf("0n");
  30.     return 0;
  31. }
Parsed in 0.001 seconds