自动搬运

查看原文

来自洛谷，原作者为

	zifanwang RP++

搬运于2025-08-24 22:51:43，当前版本为作者最后更新于2023-12-01 17:58:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

传送门

考虑将 $l_i$ 与 $r_i$ 连边，得到的图每个点的度数为 $2$，所以这个图是由若干个环组成的。然后发现每个 $a_i$ 只可能等于 $0$ 或 $2$。

题意，即给每条边定向，使得与其连接的两条边的方向不同的点的个数为 $\frac{k}{4}$。

考虑枚举每个环（记这个环为 $G$）上有多少个方向相同的边的连续段，那么上述点的个数就等于该值，因为这是个环，所以该值一定是偶数。考虑用生成函数优化，令：

那么 $[x^{k/8}]\prod_{G} F(G)$ 即为所求（如果 $k$ 不是 $8$ 的倍数就直接输出 $0$）。可以把这些多项式扔到一个堆里，每次取出次数最小的两个用 $\tt NTT$ 合并，时间复杂度 $O(n\log^2 n)$。

参考代码：

#include<bits/stdc++.h>
#define ll long long
#define int long long
#define mxn 500003
#define md 998244353
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define rept(i,a,b) for(int i=a;i<b;++i)
#define drep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
int power(int x,int y){
	int ans=1;
	for(;y;y>>=1){
		if(y&1)ans=(ll)ans*x%md;
		x=(ll)x*x%md;
	}
	return ans;
}
struct node{
	vector<int>a;
};
inline bool operator<(node x,node y){
	return x.a.size()>y.a.size();
}
int n,k,c,f[mxn],f1[mxn],rev[mxn];
ll ans=1,fac[mxn],ifac[mxn];
vector<int>g[mxn];
bool v[mxn];
priority_queue<node>q;
void dfs(int x){
	v[x]=1;
	c++;
	for(int i:g[x])if(!v[i]){
		dfs(i);
	}
}
inline ll C(int n,int m){
	return fac[n]*ifac[m]%md*ifac[n-m]%md;
}
void ntt(int *a,int n,int flag){
	rept(i,0,n)if(i<rev[i])swap(a[i],a[rev[i]]);
	for(int h=1;h<n;h<<=1){
		int x,y,s=power(3,499122176/h);
		for(int j=0;j<n;j+=h<<1){
			int w=1;
			for(int k=j;k<j+h;++k){
				x=a[k],y=w*a[k+h]%md;
				a[k]=(x+y)%md;
				a[k+h]=(x-y+md)%md;
				w=w*s%md;
			}
		}
	}
	if(flag==-1){
		int p=power(n,md-2);
		reverse(a+1,a+n);
		rept(i,0,n)a[i]=a[i]*p%md;
	}
}
signed main(){
	scanf("%lld",&n);
	fac[0]=1;
	rep(i,1,n)fac[i]=fac[i-1]*i%md;
	ifac[n]=power(fac[n],md-2);
	drep(i,n,1)ifac[i-1]=ifac[i]*i%md;
	for(int i=0,x,y;i<n;++i){
		scanf("%lld%lld",&x,&y);
		g[x].pb(y),g[y].pb(x);
	}
	scanf("%lld",&k);
	if(k%8||k/4>n){
		puts("0");
		return 0;
	}
	k/=8;
	rep(i,1,n)if(!v[i]){
		c=0;
		dfs(i);
		node s;
		rep(j,0,c)if(!(j&1))s.a.pb(C(c,j));
		q.push(s);
		ans=ans*2%md;
	}
	while(q.size()>1){
		node a=q.top();q.pop();
		node b=q.top();q.pop();
		node c;c.a.resize(a.a.size()+b.a.size()-1);
		int k,s;
		for(k=0,s=1;s<c.a.size();s<<=1,++k);
		rept(i,0,s)rev[i]=(rev[i>>1]>>1)|((i&1)<<(k-1));
		rept(i,0,a.a.size())f[i]=a.a[i];
		rept(i,a.a.size(),s)f[i]=0;
		rept(i,0,b.a.size())f1[i]=b.a[i];
		rept(i,b.a.size(),s)f1[i]=0;
		ntt(f,s,1);ntt(f1,s,1);
		rept(i,0,s)f[i]=f[i]*f1[i]%md;
		ntt(f,s,-1);
		rept(i,0,c.a.size())c.a[i]=f[i];
		q.push(c);
	}
	cout<<q.top().a[k]*ans%md;
	return 0;
}