题意: 给一个01串，其中一些位置是？，可以变成1或0，有一种操作， 将01串相邻位置两两相减的绝对值形成一个新数组，比如 1 0 1可以变成 1 1，问有多少种填充？的方案使得01串在经过n-1次操作后的值为1 。 题解： 相邻位置两两相减的绝对值就是这两个数的异或值，最后可以发现，第i位的数对最后的结果的贡献为C(n-1,i-1)次，因此当C(n-1,i-1)为偶数时，该位上的数不需要考虑，反之则要考虑，我们可以统计出有多少个问号在无贡献位，假设有k个，这些问号可以为1也可以为0，则方案数为2^k，再算出有多少个问号在有贡献位，最后算出这些问号需要放几个1才能使得结果为1的方案数乘上之前的2 ^k便是答案。 代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e6+5,mod=1e9+7; char s[maxn]; int vis[maxn]; ll fac[maxn]; void cal() { fac[0]=1; for(int i=1; i<maxn; i++) fac[i]=fac[i-1]*i%mod; } ll qpow(ll a,ll b) { ll ans=1; for(; b; b>>=1,a=a*a%mod) if(b&1) ans=ans*a%mod; return ans; } ll C(ll n,ll m) { if(n<m) return 0; return fac[n]*qpow(fac[n-m]*fac[m]%mod,mod-2)%mod; } int main() { cal(); while(cin>>s+1) { int n=strlen(s+1); int ans=0; ll cnt=0; ll sum=1; for(int i=1;i<=n;i++) { int d=(n-1)&(i-1); if(d==i-1) vis[i]=1; else vis[i]=0; if(vis[i]==1) { if(s[i]=='1') ans^=1; else if(s[i]=='?') cnt++; } else { if(s[i]=='?') sum=sum*2%mod; } } ll ca=0; if(ans==1) { for(int i=0;i<=cnt;i+=2) { ca=(ca+C(cnt,i))%mod; } } else { for(int i=1;i<=cnt;i+=2) { ca=(ca+C(cnt,i))%mod; } } ll res=ca*sum%mod; cout<<res<<endl; } }