题解：AT_abc433_f [ABC433F] 1122 Subsequence 2

WonderStone_ · 2025-11-24 20:13:50 · 题解

1122 Subsequence 2

题目大意

给定一个由数字组成的字符串 S。\\ 现给出对“1122 字符串”的定义：对于某字符串 T，当其满足以下条件时，就被成为“1122 字符串”。

字符串 T 中第 1 个字符至第 \frac{|T|}2 个字符均为同一数字。字符串 T 中从第 \frac{|T|}2+1 个字符到第 |T| 个字符均为 T 的第 1 个字符（表示的）数字加 1 形成的字符。

求字符串 S 中所有（不一定是连续的）子序列中为“1122 字符串”的数量，结果对 998244353 取模。\\ 若两个子序列来自不同位置，则即使其字符串内容相同，也应分别计数。

思路分析

考虑枚举 S 中满足条件的子序列的左半段最后一个字符的位置（第 \frac{|T|}2 个字符）。\\ 假设这是知道的唯一条件，即设该位置字符必选，考虑在这种情况下计算符合条件的子序列数量。

假设当前答案子序列的左半段最后一个字符的位置（在原字符串中）为 i，则该字符为 S_i。\\ 记 i 的左侧（包含 i）与 S_i 相同的字符有 a 个，i 的右侧与 S_i+1 相同的字符有 b 个，在 i 的左、右侧都会分别选取 l 个字符（则有 $\begin{cases} l \le a \ 1 \le b \ \end{cases}

，换句话说，就是 $l \le \min(a,b)$）。$\\

因此，i 的左侧（包含 i）需要在 a-1（因为第 i 个字符必选）个字符中选 l 个，i 的右侧需要在 b 个字符中选 l 个，因此总方案就有 C_{a-1}^{l-1} \cdot C_b^l 种。

则以 S_i 为答案左半段最后一个字符时，对总数的贡献为：\\

\begin{aligned} \sum_{l=1}^{\min(a,b)}C_{a-1}^{l-1} \cdot C_b^l &=\sum_{l=1}^{\min(a,b)}C_{a-1}^{a-l} \cdot C_b^l\\ &=C_{a+b-1}^a \end{aligned}

大家看着这个转移可能会很迷惑，因此在此做出解释：

第一步只变了一处，依靠的是 C_x^y=C_x^{y-x}。
第二步注意到式子被表现成了 \sum_{i=0}^{k} C_m^i \cdot C_n^{k-i} 的形式，因此根据 范德蒙恒等式，可以化为 C_{m+n}^k 的形式。

最后就很简单了，逆元预处理阶乘后借助公式求解组合数即可。

代码详解

#include<bits/stdc++.h>
#define int long long
#define mod 998244353
using namespace std;
string s;
unordered_map<char,int> frt,bck; //当前字符在其位置前、后出现的次数
int n,fac[2000005]={1},inv[2000005],ans;
int pows(int a,int b,int p){
    int now=1;
    while(b>0){
        if(b&1) now=now*a%p;
        a=a*a%p;
        b>>=1;
    }
    return now;
}
//利用预处理数组计算组合数
int cxy(int x,int y){
    return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>s;
    n=s.size();
    s=" "+s;
    //逆元预处理
    for(int i=1;i<=2000000;i++) fac[i]=fac[i-1]*i%mod;
    inv[2000000]=pows(fac[2000000],mod-2,mod);
    for(int i=1999999;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
    //先假设所有字符都在答案后半段
    for(int i=1;i<=n;i++) bck[s[i]]++;
    //O(|S|)计算答案
    for(int i=1;i<=n;i++){
        frt[s[i]]++,bck[s[i]]--;
        ans=(ans+cxy(frt[s[i]]+bck[s[i]+1]-1,frt[s[i]]))%mod; //公式解释见上文
    }
    cout<<ans;
    return 0;
}