【学习笔记】[ARC156E] Non-Adjacent Matching

首先，记$S=\sum X_i$，那么恰好有$\frac{S}{2}$条边（$S$为偶数）；序列 { X i } \{X_i\} {Xi​}合法的充要条件是：

• 对于任意$i$，满足$X_i+X_{i+1}\le \frac{S}{2}$

这种东西 Kidulthood 就很会猜，而我就没有这么好的直觉了😅

然后考虑容斥$X_i+X_{i+1}>\frac{S}{2}$的位置，显然这构成了一个连续段，并且长度不超过$2$。

考虑每一段的生成函数是什么。

$1.1$ 总方案数

每一段的生成函数是$\frac{1-x^{m+1}}{1-x}$，因此$GF$为：

$$(1-x^{m+1}{)}^n(\sum \left(\genfrac{}{}{0ex}{}{i+n-1}{n-1}\right)x^i)$$

枚举前面那一项，后面用前缀和算即可。注意算的是偶次方项的系数，复杂度$O(nm)$。

$1.2$ 只有一个位置不合法

考虑容斥的$i,i+1$构成一段，则枚举$S$后的$GF$为：

$$(\sum _{\frac{S}{2}<i\le 2m}(\min (m,i)-\max (i-m,0)+1)x^i)(1-x^{m+1}{)}^{n-2}(\sum \left(\genfrac{}{}{0ex}{}{i+n-3}{n-3}\right)x^i)$$

枚举第一项即可，其中第二项的取值只有常数个，对于$i>\frac{S}{2}$的条件 只要保证第一项的次数大于后两项的次数之和即可。复杂度$O(m)$。

$1.3$ 有两个位置不合法

枚举中间的数和两边中较小的数之和，以及两边中较大的数的值，然后直接算。复杂度$O(m^2)$。

总复杂度$O(nm)$。

$\text{remark}$ 看似要枚举的东西很多，但是借助$GF$可以发现实际上要枚举的东西很少。

#include
#define ll long long
#define pb push_back
#define fi first
#define se second
#define db double
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N=3005;
const int M=3005*3005;
const int mod=998244353;
int n,m,K;
ll fac[M],inv[M],sm[M],sm2[M],sm3[M];
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;
}
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;
}
void init(int mx){
    fac[0]=1;for(int i=1;i<=mx;i++)fac[i]=fac[i-1]*i%mod;
    inv[mx]=fpow(fac[mx]);for(int i=mx;i>=1;i--)inv[i-1]=inv[i]*i%mod;
    for(int i=0;i<=mx;i++){
        sm[i]=binom(i+n-1,n-1),sm2[i]=binom(i+n-3,n-3),sm3[i]=binom(i+n-4,n-4);
        if(i>=2)sm[i]=(sm[i]+sm[i-2])%mod,sm2[i]=(sm2[i]+sm2[i-2])%mod,sm3[i]=(sm3[i]+sm3[i-2])%mod;
    }
}
ll res1,res2,res3;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>K,init(K+n);
    for(int i=0;i<=n;i++){
        int j=K-i*(m+1),sgn=(i&1)?-1:1;
        if(j<0)continue;
        if((i*(m+1)+j)%2)j--;
        if(j>=0)add(res1,sgn*binom(n,i)%mod*sm[j]);
    }
    for(int i=2;i<=2*m;i++){
        for(int j=0;j*(m+1)<i;j++){
            int k=min(i-j*(m+1)-1,K-i-j*(m+1)),sgn=(j&1)?-1:1;
            if(k<0)continue;
            if((i+j*(m+1)+k)%2)k--;
            if(k>=0)add(res2,sgn*(min(m,i)-max(i-m,0)+1)*binom(n-2,j)%mod*sm2[k]);
        }
    }
    for(int i=2;i<=2*m;i++){
        for(int j=0;j<=min(i-1,m);j++){
            int l=max(0,i-m),r=min(m,j);
            if(l<=r){
                for(int k=0;k*(m+1)+j<i;k++){
                    int mx=min(K-i-j-k*(m+1),i-j-k*(m+1)-1),sgn=(k&1)?-1:1;
                    if(mx<0)continue;
                    if((i+j+k*(m+1)+mx)%2)mx--;
                    if(mx>=0){
                        add(res3,2*sgn*(r-l+1)*binom(n-3,k)%mod*sm3[mx]);
                        if(l<=j&&j<=r)add(res3,-sgn*binom(n-3,k)%mod*sm3[mx]);
                    }
                }
            }
        }
    }
    res1=(res1-n*res2+n*res3)%mod;
    cout<<(res1+mod)%mod;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73