AGC058D Yet Another ABC String

简单计数。

考虑容斥，可以发现钦定若干位置违反限制后这些钦定的长为三的段之间是可以重叠的。因此我们考虑每个极长的连续的被钦定的段，假设长度是 $l$ ，考虑计算它的容斥系数。

可以发现对于这一段，它内部两个相邻被钦定的点之间要么在串中相邻，要么相隔一个空位，不然无法满足整个段是连续被钦定的段。因此类似斐波那契容斥系数的递推可以写作

$f_l = -f_{l - 1} - f_{l - 2}$

其中 $f_3 = -1,f_4 = 1$ ，可以容易地发现对于所有 $3k + 1$ 型，容斥系数为 $1$ ，所有 $3k$ 型，容斥系数为 $-1$ 。

然后可以发现，对于每个长为 $3k + 1$ 的钦定段，它的字符序列仅取决于第一个字符，对于每个长为 $3k$ 的，它的字符序列有 $3$ 种取法。

然后就可以写出一个简单 dp 了。具体来说，设 $f_{i,j}$ 表示前 $i$ 个字符被确定，此时共有 $j$ 个长为 $3k+1$ 的段（这里 $k$ 可以为 $0$ ），此时的所有方案乘上容斥系数的和（我们认为 $3k$ 长的段容斥系数是 $-3$ ）。可以发现答案就是 $f_{n,i}$ 乘上把剩下的字符分配给这 $i$ 个空位的方法。

设 $u = \frac{n-i}{3}$ 即已经被用来放进长为 $3$ 的整段的字母数，那么这个值就是：

$g(u,i) = \frac{i!}{(A-u)!(B-u)!(C-u)!}$

这样就获得了一个 $O(n^3)$ 的做法。

可以发现我们在 dp 的时候，可以不枚举 $k$ ，转而把基本操作看为以下三种：

加入一个长为 $1$ 的段首，系数是 $1$ 。
加入一个长为 $3$ 的段首，系数是 $-3$ 。
加入一个长为 $3$ 的段接在前面的段的后面，系数是 $1$ 。

注意第三种操作不能放在序列开头，然后就可以得到一个 $O(n^2)$ 的 dp 。

可以发现这个东西并没有必要做 dp ，可以直接枚举进行了多少次长为 $3$ 的转移，特殊判断第一次转移。

即在不考虑第一次转移的时候，令 $u = \frac{n-i}{3}$ 答案就是：

$\sum_{i = 0}^{\min\{A,B,C\}} g(u,i) \binom{u + i}{i}(-2)^{u}$

然后对第一次转移是 $3$ 和 $1$ 分别讨论一下即可。

复杂度 $O(n)$ 。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
#include <cassert>
using namespace std;
const int MAXN = 3e6 + 20;
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
const int P = 998244353;
int n;
int a , b , c;
int f[1006][1006] , J[MAXN] , iJ[MAXN];

int Pow( int x , int a ) {
    int ret = 1;
    while( a ) {
        if( a & 1 ) ret = ret * 1ll * x % P;
        x = x * 1ll * x % P , a >>= 1;
    }
    return ret;
}

int C( int a , int b ) {
    return J[a] * 1ll * iJ[b] % P * iJ[a - b] % P;
}

int pf2[MAXN];
int F( int n , int bias = 0 , int bus = 0 ) {
    int ans = 0;
    rep( i , 0 , n ) if( ( n - i ) % 3 == 0 ) {
        int us = ( n - i ) / 3;
        int g = J[i + bias] * 1ll * iJ[a - us - bus] % P * iJ[b - us - bus] % P * iJ[c - us - bus] % P;
        ans = ( ans + g * 1ll * C( us + i , i ) % P * pf2[us] ) % P;
    }
    return ans;
}

void solve() {
    cin >> a >> b >> c;
    n = a + b + c;
    J[0] = 1;
    rep( i , 1 , n ) J[i] = J[i - 1] * 1ll * i % P;
    iJ[n] = Pow( J[n] , P - 2 );
    per( i , n , 1 ) iJ[i - 1] = iJ[i] * 1ll * i % P;
    pf2[0] = 1;
    rep( i , 1 , n ) pf2[i] = pf2[i - 1] * 1ll * ( P - 2 ) % P;
    cout << ( ( P - 3 ) * 1ll * F( n - 3 , 0 , 1 ) + F( n - 1 , 1 ) ) % P << endl;
}

signed main() {
    srand(time(0));
//    int T;cin >> T;while( T-- ) solve();
    solve();
}