http://codeforces.com/contest/314/problem/E
题意：
原本有一个合法的括号序列
擦去了所有的右括号和部分左括号
问有多少种填括号的方式使他仍然是合法的括号序列
括号有25种，序列长度<=1e5
传统的做法：
令dp[i][j]表示当前到第i个字符，现在还有j个左括号
若第i+1个字符是左括号，则能转移到dp[i+1][j+1]
若第i+1个字符是问号，则能转移到dp[i+1][j-1]与dp[i+1][j+1]
时间复杂度为O(n^2)
换种思路
再看这道题，他与传统的括号序列的不同之处是他擦去了所有的右括号
令dp[k][i]表示 假设括号只有一种，前k个里面，填了i个右括号的方案数
如果第i个是问号
若当前可以填左括号 dp[k][i]+=dp[k-1][i]
若当前可以填右括号 dp[k][i]+=dp[k-1][i-1]
dp[n][n/2]就是如果只有一种括号，使序列合法的方案数
现在有25种括号，假设序列中已有q个左括号
那么最终答案=25^(n/2-q) * dp[n][n/2]
这个感觉上去也是n^2的
首先把第一维压去，解决空间问题
考虑j的枚举范围
前i个里面，至多有i/2 [下取整] 个右括号
至多可以填m个左括号，所以至少有i-n/2个右括号
平摊复杂度我就不知道了
对2^32取模相当于unsigned int 自然溢出
然后就过了，跑的还很快
#include<cstdio> using namespace std; #define N 100002 char s[N]; unsigned int f[N<<]; int main()
{
int n;
scanf("%d",&n);
if(n&)
{
putchar('');
return ;
}
scanf("%s",s+);
int m=n>>,q=;
f[]=;
for(int i=;i<=n;++i)
if(s[i]=='?')
for(int j=i>>;j && j>=i-m;--j) f[j]+=f[j-];
else q++;
unsigned int ans=f[m];
for(int i=;i<=m-q;++i) ans*=;
printf("%u",ans);
}