luogu P4221 [WC2018]州区划分

本文主要是介绍luogu P4221 [WC2018]州区划分，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题面传送门
判欧拉回路写错调了一个多小时
首先可以\(O(2^nm)\)处理出哪些是可以选的就有了\(O(n3^n)\)的爆枚子集的做法。
不难想到子集卷积，但是子集卷积是卷两个没有关系的数组，但是这个是自己卷自己。
容易发现一个数枚举子集的过程是不可能从二进制和它个数相同的数拿答案的，这就意味着同一层算答案的时候是互不干扰的。
所以可以直接卷。
然后还有一个问题就是要除一个数。
很抱歉我并不会什么奇怪的科技，所以只能写那种FWT回去除了再FWT回来的东西。
时间复杂度\(O(2^nn^2)\)
code:

#include<bits/stdc++.h>
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define re register
#define RI re int
#define ll long long
#define db double
#define lb long db
#define N 21
#define K (1<<N)
#define mod 998244353
#define Mod 998244352
#define eps (1e-4)
#define U unsigned int
#define it iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define d(x,y) (n*(x-1)+(y))
using namespace std;
int n,m,k,p,x[N*N+5],y[N*N+5],In[N+5],W[K+5],H[K+5],cnt,un,wn,Fl,lg[K+5],fa[K+5],F1[N+1][K+5],F2[N+1][K+5];ll G[K+5],Inv[K+5];
I ll mpow(ll x,int y=mod-2){ll Ans=1;while(y) y&1&&(Ans=Ans*x%mod),y>>=1,x=x*x%mod;return Ans;}
I void OR(int *A,int n,int Fl){
	RI i,j,h;for(i=2;i<=n;i<<=1){
		for(j=0;j<n;j+=i) for(h=j;h<j+i/2;h++) A[h+i/2]=(1ll*A[h+i/2]+mod+A[h]*Fl)%mod;
	}
}I int Getfa(int x){return x==fa[x]?x:fa[x]=Getfa(fa[x]);}
I void merge(int x,int y){un=Getfa(x);wn=Getfa(y);un^wn&&(fa[un]=wn,cnt--);}
int main(){
	freopen("1.in","r",stdin);
	RI i,j,h;scanf("%d%d%d",&n,&m,&p);k=1<<n;for(i=1;i<=m;i++) scanf("%d%d",&x[i],&y[i]);for(i=1;i<=n;i++)scanf("%d",&W[i]);for(i=1;i<k;i++) lg[i]=lg[i/2]+1;
	for(i=1;i<k;i++)H[i]=H[i>>1]+(i&1),G[i]=(G[i^(i&-i)]+W[lg[i&-i]])%mod;
	for(i=0;i<k;i++){
		Me(In,0);for(j=1;j<=n;j++) fa[j]=j;cnt=H[i];G[i]=mpow(G[i],p);Inv[i]=G[i]?mpow(G[i]):1;for(j=1;j<=m;j++) i>>(x[j]-1)&1&&i>>(y[j]-1)&1&&(merge(x[j],y[j]),In[x[j]]^=1,In[y[j]]^=1);
		for(Fl=j=1;j<=n;j++) i>>(j-1)&1&&(Fl&=In[j]^1);F1[H[i]][i]=G[i]*(Fl^1||cnt^1);
	}F2[0][0]=1;OR(F2[0],k,1);for(i=1;i<=n;i++){
		OR(F1[i],k,1);for(j=1;j<=i;j++) for(h=0;h<k;h++) F2[i][h]=(F2[i][h]+1ll*F1[j][h]*F2[i-j][h])%mod;OR(F2[i],k,-1);
		for(j=0;j<k;j++) F2[i][j]=1ll*F2[i][j]*Inv[j]%mod;OR(F2[i],k,1);
	}OR(F2[n],k,-1);printf("%d\n",F2[n][k-1]);
}

这篇关于luogu P4221 [WC2018]州区划分的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！