题解：AT_abc433_f [ABC433F] 1122 Subsequence 2

· · 题解

赢麻了，前几天刚好学了范德蒙卷积。

范德蒙恒等式有一个变式是：

\sum_kC_n^kC_m^k=C_{n+m}^{n}

利用对称性可以得到最原始的式子，组合意义可以轻松证明，就不说了。

回到原题，考虑枚举每一个串的分界点。

这里我们设 n 为分界点前面包括分界点的某元素出现次数，m 为分界点后面对应元素出现次数。

分界点确定后，方案数就是对于每个 k 前面这个元素中选择 k-1 个与后面对应元素中选择 k 个的方案数之积的和。

列成式子就是：

\sum_kC_{n-1}^{k-1}C_m^k=C_{n+m-1}^n

这个的推导和上面那个变式差不多，一样利用对称性后就可以得到可以套用最原始式子的形式。

然后 n 和 m 可以前缀和求，预处理组合数，于是可以做到线性。

void solve(){
    string s;
    cin>>s;
    int n=s.size();
    s=" "+s;
    for(int i=1;i<=n;i++)
    for(int j=0;j<10;j++)
    qzh[i][j]=qzh[i-1][j]+(j==s[i]-'0');
    for(int i=n;i>=1;i--)
    for(int j=0;j<10;j++)
    hzh[i][j]=hzh[i+1][j]+(j==s[i]-'0');
    int ans=0;
    for(int i=1;i<=n;i++){
        if(s[i]=='9')continue;
        int x=qzh[i][s[i]-'0'];
        int y=hzh[i][s[i]-'0'+1];
        if(x==0||y==0)continue;
        ans+=C(x+y-1,x);
        ans%=mod;
    }
    cout<<ans;
}
// 开战与停战，究竟哪边才正确？哪边才符合正义？
// 能对此感到困惑的人可说还算幸运。大部分的人早就将一切都赌在预定会开始的战争上，所以他们只能相信自己选择的道路才是正义。