题解：P11487 「Cfz Round 5」Gnirts 10
A2_Zenith
·
·
题解
挺好的题，来写题解了！
首先，我们可以想到，要对答案是 i 的 01 序列 T 计数。不妨设这样的串的数量是 F(i)，那么答案是 \sum\limits_{i=1}^niF(i)。
令 Pre_i 为 S 的长度为 i 的前缀。
考虑对 S 中长度为 i 的前缀检查一个 01 串 T 是否合法。我们不难想到一个正确的贪心：设当前匹配到 s_i，设 s_i 与 T_p 匹配，那么 s_{i+1} 匹配到 T_p 往后第一个等于 s_{i+1} 的位置，没有那么整个前缀就匹配失败了。
那么我们将 T 划成若干个由极长的 0/1 组成的连续段（伏笔 1），不难发现这时的子序列要么在某一段内一点不取，要么就取一段前缀（其实可以合并成一种情况）。
发现若 T 中有 Pre_i 做为前缀，那么其一定是在 Pre_i 中插入若干个 0/1 连续段的方式生成的。怎么不重不漏的插呢？不妨对于相邻的两个字符讨论。
$01$：只能插 $0$。因为是前缀嘛。
$10$：只能插 $1$，原因同上。
$11$：只能插 $0$，原因同上。
这个限制可以规约成：设相邻两个字符中右边的那个是 $x$，那么中间只能填 $1-x$。
不难发现这个限制能够以一种成功的方式归约到 $1$ 前面的部分与 $Pre_p$ 后面的部分。（这里假设我们在算 $F(p)$。）
原因很简单：对于 $1$ 前面的部分，肯定不能与之相同，正好符合我们的这个条件；
对于 $p$ 后面的部分，其肯定不能与 $p+1$ 相同，不然答案肯定是 $p+1$ 或者更多。$p=n+m$ 的情况另算。
那么我们设现在有 $C_0$ 个可以插 $0$ 的空隙，$C_1$ 个可以插 $1$ 的空隙，已经用掉 $S_0$ 个 $0$，$S_1$ 个 $1$ 了。
那么答案就是 $F(m-S_0,C_0) \times F(n-S_1,C_1)$。其中 $F(n,k)=\dbinom{n+k-1}{k-1}$，但是 $F(0,0) =1$。
直接预处理组合数然后 $O(n+m)$ 算出就好了。
对于 $p=n+m$ 的情况：考虑 $S$ 中是否有 $n$ 个 $1$ 与 $m$ 个 $0$，有的话就给总答案加上 $n+m$。
~~不值得注意的是，这玩意在赛时卡了我快半个小时。~~
就做完了。
~~欢迎大家多多膜拜我的学长/IOIAKer @Sharpsmile，他以 0.01h 的优势拿下了本场比赛的 rk1。~~
```cpp
#include<bits/stdc++.h>
#define int long long
#define doub long double
#define PII pair<int,int>
#define mp make_pair
#define fir first
#define sec second
#define PC __builtin_popcountll
using namespace std;
const int maxn=6e6+7;
const int mod=2933256077;
int n,m;
bool Ss[maxn];
int Fac[maxn];
int iFac[maxn];
inline int qpow(int a,int b){
int ans=1;
while(b){
if(b&1)ans=1ull*ans*a%mod;
a=1ull*a*a%mod;
b>>=1;
}
return ans;
}
inline void Init(){
Fac[0]=1;
for(int i=1;i<=n+m+5;i++)Fac[i]=1ull*Fac[i-1]*i%mod;
iFac[n+m]=qpow(Fac[n+m],mod-2);
for(int i=n+m-1;i>=0;i--)iFac[i]=1ull*iFac[i+1]*(i+1)%mod;
}
inline int C(int n,int m){
if(n<0||m<0||n<m)return 0;
return 1ull*Fac[n]*iFac[m]%mod*iFac[n-m]%mod;
}
inline int F(int n,int m){
if(n<0||m<0)return 0;
if(n==0&&m==0)return 1;
return C(n+m-1,m-1);
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
cin>>n>>m;
Init();
for(int i=1;i<=n+m;i++){
char t;
cin>>t;
Ss[i]=t-'0';
}
int C0=0,C1=0;
int S0=0,S1=0;
int ans=0;
for(int i=0;i<n+m;i++){
if(i){
if(Ss[i]==0)S0++;
else S1++;
}
if(Ss[i+1]==0)C1++;
else C0++;
ans=(ans+1ull*i*F(m-S0,C0)%mod*F(n-S1,C1)%mod)%mod;
}
if(Ss[n+m]==0)S0++;
if(Ss[n+m]==1)S1++;
if((S0==m)&&(S1==n))ans+=(n+m);
ans%=mod;
cout<<ans<<endl;
return 0;
}
```