\(\text{Problem}:\)Unhappy Hacking
\(\text{Solution}:\)
显然，打出长度为 \(m\) 的 \(2^{m}\) 种不同 \(01\) 串的方案数是一样的（感性证明，退格对答案的影响是等价的，而 \(0\) 和 \(1\) 可以互相替换）。故求出所有长度为 \(m\) 的方案，最后除以 \(2^{m}\) 即可。
设 \(f_{i,j}\) 表示操作 \(i\) 次当前长度为 \(j\) 的方案数，有转移：
- \(f_{i,j}=2f_{i-1,j-1}+f_{i-1,j+1},j\geq 1\)
- \(f_{i,0}=f_{i-1,0}+f_{i-1,1},j=0\)
总时间复杂度 \(O(n^{2})\)。
\(\text{Code}:\)
#include <bits/stdc++.h>
#pragma GCC optimize(3)
//#define int long long
#define ri register
#define mk make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define is insert
#define es erase
#define vi vector<int>
#define vpi vector<pair<int,int>>
using namespace std; const int N=5010, Mod=1e9+7;
inline int read()
{
int s=0, w=1; ri char ch=getchar();
while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) w=-1; ch=getchar(); }
while(ch>=‘0‘&&ch<=‘9‘) s=(s<<3)+(s<<1)+(ch^48), ch=getchar();
return s*w;
}
int n,m,F[N][N]; char s[N];
signed main()
{
F[0][0]=1;
n=read();
scanf("%s",s), m=strlen(s);
for(ri int i=1;i<=n;i++)
{
for(ri int j=1;j<=i;j++)
{
F[i][j]=(2ll*F[i-1][j-1]%Mod+F[i-1][j+1])%Mod;
}
F[i][0]=(F[i-1][0]+F[i-1][1])%Mod;
}
int now=1;
for(ri int i=1,inv2=(Mod+1)/2;i<=m;i++) now=1ll*now*inv2%Mod;
printf("%d\n",1ll*F[n][m]*now%Mod);
return 0;
}