AGC051D C4

想了两小时 $O(n)$ 才发现 $O(n\log n)$ 可过。做法非常垃圾。

经过边的次数固定看起来非常复杂，经过点的次数会好考虑很多，假设四个点的次数分别是 $a,b,c,d$ ，那么答案其实就是 $\binom{a+c-1}{a-1} \binom{b+d}{b}$ ，因为总是在 $(a,c),(b,d)$ 之间切换。

如果边的次数给定了，那么其实点的次数是确定的，每个点经过次数分别是 $\frac{a+b}{2},\frac{b+c}2,\frac{c+d} 2,\frac {d+a}2$ 。但是这个变换并不满秩，点的次数固定时边的次数有若干可能，具体来讲总是可以同时增加 $1,3$ 边并减少 $2,4$ 边来得到相同的方案。

那么其实只要能在点的经过次数固定的情况下固定 $1$ 边被经过多少次就行了，得到的就是答案。也就是说，需要求出一个点的序列，满足四种点经过次数为 $a,b,c,d$ ，同时 $A \to B,B \to A$ 的次数和为读入的一个值 $x$ 。下面假设四个点分别是 $A,B,C,D$ 。

我们可以先固定路径中的所有 $A$ ，会有 $s=a+1$ 个。接下来考虑枚举有多少 $B$ 单独占在两个 $A$ 之间，再枚举 $D$ 单独占再两个 $A$ 之间，剩下的位置必须有至少两个 $B/D$ ，都可以用组合数计算：

$$\sum_{k=0}^{s-1} \binom{s-1} k \sum_{t=0}^{s-k-1} \binom{s-k-1}t \binom{2(s-1-k-t)}{x-2k} \binom{b+d-s}{s-2-t-k} \binom{b+d-2s+2+t+k}{b+k-x}$$

该式可以用 NTT 优化，复杂度 $O(n\log n)$ 。

#include "bits/stdc++.h"
#include "atcoder/all"
using namespace std;
#define fi first
#define se second
#define vi vector<int>
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define mp make_pair
#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 mem( a ) memset( a , 0 , sizeof (a) )
#define all( x ) x.begin() , x.end()
//#define int long long
// #pragma GCC optimize(2)
typedef long long ll;
const int MAXN = 2e6 + 10;
const int P = 998244353;
int ab , bc , cd , da;
int a , b , c , d;

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;
}

void Inc( int&a , int b ) {
    a = ( a + b < P ? a + b : a + b - P );
}

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

int giJ( int x , int coef = 0 ) {
    return x < 0 ? coef : iJ[x];
}
int gJ( int x ) {
    return x < 0 ? 0 : J[x];
}

void solve() {
    J[0] = 1;
    rep( i , 1 , 2000000 ) J[i] = J[i - 1] * 1ll * i % P;
    iJ[2000000] = Pow( J[2000000] , P - 2 );
    per( i , 2000000 , 1 ) iJ[i - 1] = iJ[i] * 1ll * i % P;
    cin >> ab >> bc >> cd >> da;
    if( ( ab + da & 1 ) || ( bc + ab & 1 ) || ( bc + cd & 1 ) || ( cd + da & 1 ) ) {
        puts("0"); return;
    } 
    // cout << C( ab + cd , ab ) * 1ll * C( bc + da , bc ) % P << endl;
    a = ( ab + da >> 1 ) , b = ( ab + bc >> 1 ) , c = ( bc + cd >> 1 ) , d = ( cd + da >> 1 );
    int s = a + 1 , x = ab;

    vector<int> A( s ) , B( s );
    rep( k , 0 , s - 1 ) 
        A[k] = J[s - 1 - k] * 1ll * giJ( x - 2 * k ) % P * giJ( b + k - x ) % P * iJ[k] % P * iJ[s - 1 - k] % P;
    rep( t , 0 , s - 1 ) B[t] = iJ[t] * 1ll * giJ( 2 * s - 2 - 2 * t - x ) % P * giJ( d - 2 * s + t + 2 + x ) % P;
    vi re = atcoder::convolution( A , B );
    int ans = 0;
    rep( p , 0 , s - 1 ) {
        int tr = re[p] * 1ll * iJ[s - 1 - p] % P * J[2 * s - 2 - 2 * p] % P * 
        gJ( b + d - s ) % P * giJ( s - 2 - p ) % P * giJ( b + d - 2 * s + 2 + p ) % P * 
        gJ( b + d - 2 * s + p + 2 ) % P * J[s - 1] % P;
        ans = ( ans + tr ) % P;
    }
    cout << ans << endl;
}

signed main() {
//	 freopen("in","r",stdin);
	// freopen("fout","w",stdout);
	// int T;cin >> T;while( T-- ) solve();
	solve();
}