#186 path（容斥原理+状压dp+NTT）

时间：2021-12-14 16:55:15

　　首先只有一份图时显然可以状压dp，即f[S][i]表示S子集的哈密顿路以i为终点的方案数，枚举下个点转移。

　　考虑容斥，我们枚举至少有多少条原图中存在的边（即不合法边）被选进了哈密顿路，统计出这个情况下的哈密顿路数量就可以容斥了。

　　考虑暴力，显然是枚举在每张图中选择了哪些不合法边。注意到当固定了某些边被选择后，可以将这些边两端的点缩掉，缩完点之后因为已经进行了容斥，可以假装这是个完全图，哈密顿路径数量显然就是剩余点数的阶乘了，于是只需要考虑选择边的方案数。

　　先考虑在一张图中选择边的方案数。之前已经求出了某个子集用一条链串起来的方案数，于是再来一个子集状压dp就搞定了。现在固定了每张图选择边的数量之和，考虑一下生成函数之类的东西容易发现求个多项式快速幂即可。可以直接在点值表示下进行。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define P 998244353

#define N 14

#define M 2100000

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

int n,m,k,a[N][N],f[1<<N][N],h[1<<N],g[N][1<<N],u[M],size[1<<N],fac[M],r[M],ans;

void inc(int &x,int y){x+=y;if (x>=P) x-=P;}

int ksm(int a,int k)

{

	int s=1;

	for (;k;k>>=1,a=1ll*a*a%P) if (k&1) s=1ll*s*a%P;

	return s;

}

int inv(int a){return ksm(a,P-2);}

void DFT(int *a,int n,int g)

{

	for (int i=0;i<n;i++) r[i]=(r[i>>1]>>1)|(i&1)*(n>>1);

	for (int i=0;i<n;i++) if (i<r[i]) swap(a[i],a[r[i]]);

	for (int i=2;i<=n;i<<=1)

	{

		int wn=ksm(g,(P-1)/i);

		for (int j=0;j<n;j+=i)

		{

			int w=1;

			for (int k=j;k<j+(i>>1);k++,w=1ll*w*wn%P)

			{

				int x=a[k],y=1ll*w*a[k+(i>>1)]%P;

				a[k]=(x+y)%P,a[k+(i>>1)]=(x-y+P)%P;

			}

		}

	}

}

int main()

{

	n=read(),k=read(),m=read();

	for (int i=1;i<=m;i++)

	{

		int x=read(),y=read();

		a[x][y]=a[y][x]=1;

	}

	for (int i=0;i<n;i++) f[1<<i][i]=1;

	for (int i=0;i<(1<<n);i++)

	{

		for (int j=0;j<n;j++)

		if (f[i][j])

		{

			for (int x=0;x<n;x++)

			if (!(i&(1<<x))&&a[j][x]) inc(f[i|(1<<x)][x],f[i][j]);

		}

		for (int j=0;j<n;j++) inc(h[i],f[i][j]);

	}

	for (int i=1;i<(1<<n);i++) size[i]=size[i^(i&-i)]+1;

	g[0][0]=1;

	for (int i=0;i<n;i++)

		for (int j=1;j<(1<<n);j++)

			for (int x=j;x>0;x=x-1&j)

			if ((j&-j)==(x&-x)&&i>=size[x]-1) inc(g[i][j],1ll*g[i-(size[x]-1)][j^x]*h[x]%P);

	for (int i=0;i<n;i++) u[i]=g[i][(1<<n)-1];

	int t=1;while (t<=k*n) t<<=1;

	DFT(u,t,3);

	for (int i=0;i<t;i++) u[i]=ksm(u[i],k);

	DFT(u,t,inv(3));

	int v=inv(t);

	for (int i=0;i<t;i++) u[i]=1ll*u[i]*v%P;

	fac[0]=1;for (int i=1;i<=k*n;i++) fac[i]=1ll*fac[i-1]*i%P;

	for (int i=0;i<=k*n;i++)

	if (i&1) inc(ans,P-1ll*fac[k*n-i]*u[i]%P);

	else inc(ans,1ll*fac[k*n-i]*u[i]%P);

	cout<<ans;

	return 0;

}

　　

相关文章