【学习笔记】[ARC156E] Non

学习笔记】[ARC156E] Non"/>

【学习笔记】[ARC156E] Non

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

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

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

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

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

1.1 1.1 1.1 总方案数

每一段的生成函数是 1 − x m + 1 1 − x \frac{1-x^{m+1}}{1-x} 1−x1−xm+1​，因此 G F GF GF为：

( 1 − x m + 1 ) n ( ∑ ( i + n − 1 n − 1 ) x i ) (1-x^{m+1})^{n}(\sum \binom{i+n-1}{n-1}x^i) (1−xm+1)n(∑(n−1i+n−1​)xi)

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

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

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

( ∑ S 2 < i ≤ 2 m ( min ⁡ ( m , i ) − max ⁡ ( i − m , 0 ) + 1 ) x i ) ( 1 − x m + 1 ) n − 2 ( ∑ ( i + n − 3 n − 3 ) x i ) (\sum_{\frac{S}{2}<i\le 2m}(\min(m,i)-\max(i-m,0)+1)x^i)(1-x^{m+1})^{n-2}(\sum \binom{i+n-3}{n-3}x^i) (2S​<i≤2m∑​(min(m,i)−max(i−m,0)+1)xi)(1−xm+1)n−2(∑(n−3i+n−3​)xi)

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

1.3 1.3 1.3 有两个位置不合法

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

总复杂度 O ( n m ) O(nm) O(nm)。

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

#include<bits/stdc++.h>
#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;
}