看完题目想必大家都明白了 这个数组里面只有0/1

**所以大家应该能够想到 当 1 的个数为奇数时 是不是残骸就为 1 了

所以聪明的你肯定能够想到 每一个 1 的位置都是随机的 所以我们需要考虑每一个 1 在长度为n的数组里面的位置问题

所以聪明的你肯定又能想到高中学习的排列组合 又因为是组合问题 所以聪明的你肯定能够知道是C几几的问题

所以聪明的你肯定想到了直接求的方法**

链接 https://ac.nowcoder.com/acm/contest/122913/B

#defime ll long long
ll ksm(int x,int y){
	ll res=1;
	while(y){
    if(y&1) res=res*x%mod; //判断y的奇偶
    x=x*x%mod;
    y>>=1;  // 等同于y/=2;
  	}
}

ll inv(int x){
	return ksm(x,mod-2);
}
    
ll C(int x;int y){
  ll res=1;
  for(ll i=x;i>=x-y+1;i--) res=res*i%mod;
  for(ll j=1;j<=y;j++) res=res*inv(j)%mod;
  return res;
}
void solve(){
  ll n,sum=0;
  cin>>n;
  for(int i=1;i<=n;i+=2){
    sum+=C(n,i);
  }
  cout<<sum<<"\n";
}
signed main(){
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  int T;
  cin>>T;
  while(T--){
    solve();
  }
}

聪明的你写完这串代码 高高兴兴的过了样例 兴高采烈的交了上去 然后发现它转了很久 你以为是你的电脑卡了然后刷新了一下页面重新弄提交了一下 结果还是一直转 所以 你就等了几十秒 结果弹出来一个运行超时（10001ms）

所以聪明的你开始思考你这串“完美”的代码哪里出了问题 到底是哪里出了问题呢？

想了很久 聪明的人终于想到 多次调用C使得运行时间过长 所以 聪明的你想到了预处理

所以你又写下了：

#define ll long long
ll ksm(ll x,ll y){
	ll res=1;
	x%=mod;
	while(y){
		if(y&1) res=res*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	 return res;
}

ll inv(ll x){
	return ksm(x,mod-2);
}
ll fz[N],fm[N];
void iint(){
	ll w=N-10;
	fz[0]=fm[0]=1;
	for(ll i=1;i<=w;i++){
		fz[i]=fz[i-1]*i;
		fz[i]%=mod;
	}
	fm[w]=inv(fz[w]);
	for(ll i=w-1;i>=1;i--){
		fm[i]=fm[i+1]*(i+1);
		fm[i]%=mod;
	}
}
ll C(ll n,ll m){
	if(n<m) return 0;
	return fz[n]*fm[m]%mod*fm[n-m]%mod;
}

void solve(){
	cin>>n;
	ll sum=0;
	for(int i=1;i<=n;i+=2){
		sum+=C(n,i)%mod;
	}
	cout<<sum%mod<<"\n";

}
signed main(){
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  iint();
  int T;
  cin>>T;
  while(T--){
    solve();
  }
}

写完后聪明的你看着”恭喜你成功AC此题“ 欣慰的笑了