【学习笔记】[AGC058D] Yet Another ABC String

好题，只是我做不起罢了。

一般的容斥思路：枚举位置集合$\{p_i\}$表示$S_{p_i\sim p_i+2}\in \{ABC,BCA,CAB\}$，然后算方案数。这个方法比较通用，但是在这道题中好像做不出来。

考虑上面的容斥，如果将字母看成是数字，本质上是限制了$a_i=(a_{i-1}+1)\bmod 3$。因此原序列可以被划分成若干个极长的子段，设长度为$k$的子段对应的容斥系数为$c_k$，可以得到$c_k=-c_{k-1}-c_{k-2}$，因此归纳得到：

$$c_k=\begin{cases}-1& k\bmod3=0\\1&k\bmod3=1\\0&k\bmod3=2\end{cases}$$

然后可以$O(n^2)$暴力求出答案。

这个时候组合数就没有什么优势了。考虑用三元$GF$进行化简，反复利用：
$$ \frac{1}{1-F(x)}=\sum_{i\ge 0}F(x)^i $$

每一段的$GF$：
$$ \begin{aligned}F&=-3\sum_{i\ge 1}(abc)^i+\sum_{i\ge 0}(abc)^i(a+b+c)\\&=-3abc\cdot \frac{1}{1-abc}+(a+b+c)\cdot \frac{1}{1-abc}\\&=(-3abc+a+b+c)\cdot \frac{1}{1-abc} \end{aligned} $$

设答案的生成函数为$G$。则：

$$ \begin{aligned}G&=\sum_{i\ge 0}F^i\\&=\frac{1}{1-F}\\&=\frac{1-abc}{2abc-a-b-c+1}\\&=(1-abc)\sum_{i\ge 0}(a+b+c-2abc) \end{aligned} $$

暴力枚举即可$O(n)$计算答案。

$\text{remark}$ 以后遇到这样将子段拼起来的问题可以考虑用$GF$。这个东西 [好像见过](https://blog.csdn.net/cqbzlydd/article/details/128773207?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522169737331916800222893673%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&request_id=169737331916800222893673&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~first_rank_ecpm_v1~rank_v31_ecpm-1-128773207-null-null.nonecase&utm_term=%E7%94%9F%E6%88%90%E5%87%BD%E6%95%B0&spm=1018.2226.3001.4450)

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define inf 0x3f3f3f3f
using namespace std;
const int N=3e6+5;
const int mod=998244353;
ll fac[N],inv[N],res;
int a,b,c;
ll fpow(ll x,ll y=mod-2){
    ll z(1);
    for(;y;y>>=1){
        if(y&1)z=z*x%mod;
        x=x*x%mod;
    }return z;
}
void init(int n){
    fac[0]=1;for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
    inv[n]=fpow(fac[n]);for(int i=n;i>=1;i--)inv[i-1]=inv[i]*i%mod;
}
ll binom(int x,int y){
    if(x<0||y<0||x<y)return 0;
    return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
void add(ll &x,ll y){
    x=(x+y)%mod;
}
ll calc(int a,int b,int c){
    if(a<0||b<0||c<0)return 0;
    ll res=0;
    for(int i=0;i<=min({a,b,c});i++){
        add(res,fpow(-2,i)*fac[a+b+c-2*i]%mod*inv[a-i]%mod*inv[b-i]%mod*inv[c-i]%mod*inv[i]);
    }return res;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>a>>b>>c,init(a+b+c);
    add(res,calc(a,b,c)-calc(a-1,b-1,c-1));
    cout<<(res+mod)%mod;    
}