【AtCoder Regular Contest 059 F】Unhappy Hacking
动态规划。
题目大意：
给定 $n$ 和一个 01 串 $s$。你有一个初始为空的字符串 $t$，要对其进行 $n$ 次操作，每次操作有三种：
- 在 $t$ 后面补上一个
0。 - 在 $t$ 后面补上一个
1。 - 删除 $t$ 末尾的一个字符。若 $t$ 为空串，则忽略这次操作。
问有多少种不同的操作序列，使得最后 $t=s$。
题解：
由于 $t$ 要等于 $s$，所以 $t$ 中肯定存在一个加字符的子序列，其恰好为 $s$。而剩下的操作，就是补若干个字符，然后再删掉。
我们必须保证每一时刻，补上的字符必须不多于删掉的字符，这样才不会影响子序列上的元素。这就是一个括号匹配问题。$n$ 个左括号个 $n$ 个右括号的匹配方案恰好是卡特兰数的第 $n$ 项。可以使用 $\frac{\binom{2n}n}{n+1}$。由于这里的 0 和 1 是可以任意选的，所以方案数还需要乘上 $2^n$。
我们需要在子序列的间隙中把这些东西插进去。可以用 $dp_{i,j}$ 表示前 $i$ 个间隙中插入了 $j$ 对括号的方案。转移是个卷积的形式，直接做是 $O(n^3)$ 的。可以使用多项式技巧做到 $O(n\cdot\mathrm{poly}(\log n))$，但由于这题 $n$ 比较小，直接快速幂暴力卷积即可，时间复杂度 $O(n^2\log n)$。
还有一个问题，我们可以在串的开头插入一些对空串的“浪费”操作。这里为了保证不会算重，我们规定“浪费”操作序列的最末尾一定是对空串进行的删除操作。
我们用 $g_{i,j}$ 表示做了 $i$ 个操作，当前字符串长度为 $j$ 的方案数。
那么 $g_{i,j}=2g_{i-1,j-1}$（$j\gt 0$，表示插入一个字符）。$g_{i,j}=g_{i-1,j+1}$（表示删除一个字符）。$g_{i,0}=g_{i-1,0}$（表示对空串删除一个字符）。
计算的时间复杂度为 $O(n^2)$。
我们查长度为 $k$ 的前缀的方案数，就是 $g_{k-1,0}$（前 $k-1$ 位要没有字符，最后钦定执行一次删除）。
我们枚举前面“浪费”的前缀长度，然后使用 $g$ 和 $dp$ 再进行组合就可以计算。
Code：
#include<cstdio>
#include<cstring>
typedef long long LL;
const int md=1e9+7,N=16384;
int fac[N],iv[N],n,c[5002],dp[5002],g[5002],h[5002],s[5002];
char v[N];
inline int C(int n,int m){return(LL)fac[n]*iv[m]%md*iv[n-m]%md;}
inline int pow(int a,int b){
int ret=1;
for(;b;b>>=1,a=(LL)a*a%md)if(b&1)ret=(LL)ret*a%md;
return ret;
}
void PW(int b,int n){
static int A[5002];
*dp=1;
for(;b;b>>=1){
if(b&1){
memset(A,0,sizeof A);
for(int i=0;i<=n;++i)for(int j=0;j<=i;++j)
A[i]=(A[i]+(LL)dp[j]*c[i-j])%md;
memcpy(dp,A,sizeof A);
}
memset(A,0,sizeof A);
for(int i=0;i<=n;++i)for(int j=0;j<=i;++j)
A[i]=(A[i]+(LL)c[j]*c[i-j])%md;
memcpy(c,A,sizeof A);
}
}
int main(){
scanf("%d%s",&n,v);
int L=strlen(v),k=n-L>>1;
for(int i=*fac=1;i<=2*n;++i)fac[i]=(LL)fac[i-1]*i%md;
iv[2*n]=pow(fac[2*n],md-2);
for(int i=2*n-1;~i;--i)iv[i]=(i+1LL)*iv[i+1]%md;
for(int i=0,w=1;i<=k;++i,w=w*2>=md?w*2-md:w*2)
c[i]=(LL)C(2*i,i)*iv[i+1]%md*fac[i]%md*w%md;
PW(L+1,k);
h[0]=g[0]=1;
for(int i=1;i<=2*k+1;++i){
memset(s,0,sizeof s);
for(int j=1;j<=2*k+1;++j)s[j]=g[j-1]*2%md;
for(int j=0;j<2*k+1;++j)s[j]=(s[j]+g[j+1])%md;
s[0]=(s[0]+g[0])%md;
h[i]=s[0];
memcpy(g,s,sizeof s);
}
int ans=0;
for(int i=0;i<=k;++i){
int sy=n-2*i-L;
int ch=(sy==0)?1:h[sy-1];
ans=(ans+(LL)ch*dp[i])%md;
}
printf("%d\n",ans);
return 0;
}