题意：
有三种操作，在右边添加0/1或删除最右边的数（空字符串无操作）
给出操作数\(N\)，字符串\(s\)，问有多少种方法经过\(N\)次操作后得到字符串\(S\)
思路
最开始在想三维dp，虽然发现了性质，但是没想到很好的用法
重要性质：答案与字符串内容无关，仅与字符串长度有关
定义\(f_{i,j}\)为操作\(i\)次得到长度为\(j\)的字符串的方案数
则有状态转移方程：
\[\begin{align} f_{i,j} = 2*f_{i-1,j-1}+f_{i-1,j+1} \quad (j > 0) \\ f_{i,j} = f_{i-1,j}+f_{i-1,j+1} \quad (j = 0) \end{align} \]最终答案为
\[\frac {f_{n,len(s)}}{2^{len(s)}} \]点击查看代码
void solve(){
string s;
cin >> n >> s;
m = s.size();
f[0][0] = 1;
for (int i = 1 ; i <= n ; ++i){
f[i][0] = (f[i-1][0]+f[i-1][1])%mod;
for (int j = 1 ; j <= n ; ++j){
f[i][j] = (f[i-1][j-1]*2ll+f[i-1][j+1])%mod;
}
}
ll tmp = quick_pow(2 , m);
tmp = quick_pow(tmp , mod-2);
ll ans = tmp*f[n][m]%mod;
cout << ans << "\n";
}