原文链接www.cnblogs.com/zhouzhendong/p/UOJ348.html

前言

第一次知道子集卷积可以自己卷自己。

题解

这是一道子集卷积模板题。

设 $sum[S]$ 表示点集 S 的点权和。

设 $f[S]$ 表示对点集 S 进行州区划分得到的答案，定义 $g[S]$ 在点集 S 合法时为 $(sum[S])^p$，不合法时为 0 。

则

$$f[S] = \frac{1}{(sum[S])^p}\sum_{T\subsetneq S} f[T]g[S-T]$$

这东西是个子集卷积的形式。

但是在卷的时候要调用自己。

那怎么办？

一边做子集卷积，一边得出新答案。

具体地：枚举一下集合大小 S ，每次通过之前的结果做卷积求出当前集合大小的所有集合的答案。

直接保留 FMT 后的结果，方便计算、降低时间复杂度。

具体细节见代码。

时间复杂度 $O(n^22^n)$ 。

代码

#pragma GCC optimize("Ofast","inline")

#include <bits/stdc++.h>

#define clr(x) memset(x,0,sizeof (x))

#define For(i,a,b) for (int i=a;i<=b;i++)

#define Fod(i,b,a) for (int i=b;i>=a;i--)

#define pb(x) push_back(x)

#define mp(x,y) make_pair(x,y)

#define fi first

#define se second

#define _SEED_ ('C'+'L'+'Y'+'A'+'K'+'I'+'O'+'I')

#define outval(x) printf(#x" = %d\n",x)

#define outvec(x) printf("vec "#x" = ");for (auto _v : x)printf("%d ",_v);puts("")

#define outtag(x) puts("----------"#x"----------")

#define outarr(a,L,R) printf(#a"[%d...%d] = ",L,R);\

						For(_v2,L,R)printf("%d ",a[_v2]);puts("");

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

typedef vector <int> vi;

LL read(){

	LL x=0,f=0;

	char ch=getchar();

	while (!isdigit(ch))

		f|=ch=='-',ch=getchar();

	while (isdigit(ch))

		x=(x<<1)+(x<<3)+(ch^48),ch=getchar();

	return f?-x:x;

}

const int N=23,S=1<<21,mod=998244353;

const ULL Bmod=16ULL*mod*mod;

int Pow(int x,int y){

	int ans=1;

	for (;y;y>>=1,x=(LL)x*x%mod)

		if (y&1)

			ans=(LL)ans*x%mod;

	return ans;

}

void Add(int &x,int y){

	if ((x+=y)>=mod)

		x-=mod;

}

void Del(int &x,int y){

	if ((x-=y)<0)

		x+=mod;

}

int n,m,s,p;

vector <int> e[N];

int w[N];

int cnt1[S],sum[S],f[S];

int g[N][N];

int u[N][S],v[N][S];

int check(int s){

	static int vis[N],in[N],q[N],head,tail,x;

	if (!s)

		return 0;

	clr(vis),clr(in);

	int fir=-1;

	For(i,0,n-1)

		if (s>>i&1){

			fir=i;

			break;

		}

	head=tail=0;

	q[++tail]=fir,vis[fir]=1;

	while (head<tail){

		x=q[++head];

		for (auto y : e[x])

			if (s>>y&1){

				in[y]^=1;

				if (!vis[y])

					vis[y]=1,q[++tail]=y;

			}

	}

	if (tail!=cnt1[s])

		return 1;

	For(i,0,n-1)

		if (in[i])

			return 1;

	return 0;

}

void FMT(int *a){

	For(i,0,n-1)

		For(j,0,s-1)

			if (j>>i&1)

				Add(a[j],a[j^1<<i]);

}

void IFMT(int *a){

	For(i,0,n-1)

		For(j,0,s-1)

			if (j>>i&1)

				Del(a[j],a[j^1<<i]);

}

int main(){

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

	s=1<<n;

	clr(g);

	For(i,1,m){

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

		e[x].pb(y),e[y].pb(x);

	}

	For(i,0,n-1)

		w[i]=read();

	For(i,0,s-1){

		For(j,0,n-1)

			if (i>>j&1){

				cnt1[i]++;

				sum[i]+=w[j];

			}

		f[i]=check(i);

		sum[i]=Pow(sum[i],p);

		if (f[i])

			u[cnt1[i]][i]=sum[i];

	}

	For(i,0,n)

		FMT(u[i]);

	v[0][0]=1;

	FMT(v[0]);

	For(i,1,n){

		For(k,0,s-1){

			ULL tmp=0;

			For(j,0,i-1){

				tmp+=(LL)v[j][k]*u[i-j][k];

				if (tmp>=Bmod)

					tmp-=Bmod;

			}

			v[i][k]=tmp%mod;

		}

		IFMT(v[i]);

		For(k,0,s-1)

			if (cnt1[k]==i)

				v[i][k]=(LL)v[i][k]*Pow(sum[k],mod-2)%mod;

			else

				v[i][k]=0;

		FMT(v[i]);

	}

	IFMT(v[n]);

	cout<<v[n][s-1]<<endl;

	return 0;

}

巴特西

UOJ#348. 【WC2018】州区划分

前言

题解

代码

最新文章

热门文章