2025牛客WC4-C-Tokitsukaze and Balance String (hard) · znzryb
## 思路讲解
[https://www.luogu.com/article/wa8c5zfe](https://www.luogu.com/article/wa8c5zfe) 还有一种差分想法，更加简洁，挺好的
10就是在差分数组中有一个-1，01就是差分数组中有一个1，把差分数组加起来，就能得到01数量-10数量的值，然后根据差分的结论，我们就知道差分总值只和首项和末项有关。
> 首先根据上题，我们需要发现两个结论：
1） 首尾相同的字符串一定是平衡的。
2） 首尾不相同的字符串一定是不平衡的。
这是为什么那？
直接证明这个结论比较难，可以这么想，大家可以想象一个都是0序列，将里面的0变为1（通过这一操作可以生成任何序列）会对10，01数量造成什么变化那？~~（其实我也不是很会证明，大家就随便看看吧）~~
我们发现，只有在对空情况的操作时，才会产生不平衡这样的问题
而且对空情况的左右两种镜像情况分别为一组，这两组中的任意两对都是互相抵消的（比如10++ && 01++ 就会使数列平衡）
那么其实就完成了，头尾都是0的情况嘛所有操作都使数列保持平衡，头尾都是1的情况对空操作也就抵消了，那么就得到了上述的结论。
有了这个结论以后剩下的就简单了，剩下的就看代码吧，关键地方有注释，然后注意特判只有单个字母的情况。
## AC代码
AC
[https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75411197](https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75411197)
```cpp
// Problem: Tokitsukaze and Balance String (hard)
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/95336/C
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(5e18)+3,mod=static_cast<ll>(1e9)+7;
ll N,T;
char S[MAXN];//Sd[MAXN];
ull ans=0,pow2[MAXN];
inline void solve(){
cin>>N;
ans=0;
ll cnt=0;
FOR(i, 1, N){
cin>>S[i];
if(S[i]=='?') ++cnt;
// Sd[i]=S[i];
}
if(N==1){
if(S[1]!='?') cout<<1<<'\n';
else cout<<2<<'\n';
return;
}
if(S[1]=='?' && S[N]=='?'){
ans+=2*pow2[cnt-2]*(N-2); // ?为0，0 1，1的情况
//cerr<<ans<<'\n';
ans%=mod;
ans+=4*pow2[cnt-2]; // ?,? 1,0 0,1的情况(两种情况，每种情况有两种位置，所以*4)
//cerr<<ans<<'\n';
ans%=mod;
}else if(S[1]=='?' || S[N]=='?'){
ans+=pow2[cnt-1]*(N-2);
ans%=mod;
ans+=2*pow2[cnt-1];
ans%=mod;
}else{
if(S[1]!=S[N]){
ans=2*pow2[cnt];
ans%=mod;
}else{
ans=pow2[cnt]*(N-2);
ans%=mod;
}
}
cout<<ans%mod<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>T;
pow2[0]=1;
FOR(i,1,MAXN-5){
pow2[i]=(pow2[i-1]*2)%mod;
}
while(T--){
solve();
}
return 0;
}
/*
AC
*/
```
## 心路历程（WA，TLE，MLE……）