题解：AT_abc433_f [ABC433F] 1122 Subsequence 2

· · 题解

最后一次打 abc 了，罕见地切了数数题（虽然也不是啥难题），写篇题解纪念一下。

首先考虑一个简化版的问题：有一个 01 串，问有多少个长度为偶数的子序列，满足前一半是 0，后一半是 1。

考虑枚举最后一个 0，钦定这个 0 必须选，假设这个位置是 i，设 i 前面的 0 的个数为 c_0，i 后面的 1 的个数为 c_1，那么贡献为：

\sum \limits_{i=1}^{\min(c_0,c_1)} \binom{c_0-1}{i-1}\binom{c_1}{i}

根据范德蒙德卷积，这个式子就等于 \binom{c_0+c_1-1}{c_0}，那么预处理组合数就可以做到 \mathcal O(n)。

那么只要把原串中的相邻的数字挑出来，当成 01 串做就好了，每个位置至多被算两次，时间复杂度 \mathcal O(n)。

代码：


#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,mod=998244353;
int n,fac[2*N],inv[2*N],facinv[2*N],ans;
string s,t[15];
void init(){
    fac[0]=inv[1]=facinv[0]=1;
    for(int i=1;i<=2*n;i++) fac[i]=1ll*fac[i-1]*i%mod;
    for(int i=2;i<=2*n;i++) inv[i]=(1ll*inv[mod%i]*(-mod/i)%mod+mod)%mod;
    for(int i=1;i<=2*n;i++) facinv[i]=1ll*facinv[i-1]*inv[i]%mod;
}
int C(int n,int m){
    if(n<0||m<0||m>n) return 0;
    return 1ll*fac[n]*facinv[n-m]%mod*facinv[m]%mod;
}
void solve(string s){
    int n=(int)s.size(),cnt0=0,cnt1=0;
    s=' '+s;
    for(int i=1;i<=n;i++) cnt1+=s[i]-'0';
    for(int i=1;i<=n;i++)
        if(s[i]=='0'){
            cnt0++;
            ans=(ans+C(cnt0+cnt1-1,cnt0))%mod;
        }
        else cnt1--;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>s;
    n=s.size();
    s=' '+s;
    init();
    for(int i=1;i<=n;i++)
        t[s[i]-'0'].push_back('1'),t[s[i]-'0'+1].push_back('0');
    for(int i=1;i<10;i++) solve(t[i]);
    cout<<ans<<'\n';
    return 0;
}