loj2340(wc2018t2)题解

Feb 10, 2018 14:20 · 293 words · 2 minutes read 题解 loj FWT 状压 集合幂级数

我会子集并卷积,我会子集对称差卷积,可惜我没认真看vfk论文所以我不会子集卷积,结果考场上我就没想出来,只打了50分……

前置技能:子集卷积。不会的可以看一看2015国家集训队论文集里面vfk的那篇。

首先题面写得非常sb,你可以理解为不存在欧拉回路或者不联通的时候州是合法的。

让$g_S$表示S中的城市作为一个州是否合法,$W_S$表示S中城市的总人口数,$f_S$代表只考虑S中城市的答案,那么可以很轻松地得到这样一个式子:

$$f_S=\sum_{U\cup V=S\\U\cap V=\emptyset} f_Ug_V(\frac{W_V}{W_S})^p$$

然后你可以用一个$O(3^n)$的dp把它算出来,获得50分。

注意到这个长得很像一个子集卷积的形式,但是左右两边都有f,而且有一边还有一个$W_S$,不方便用多项式求逆的方法解决,如果分治的话,复杂度是$O(n^32^n)$的,还是跑不出剩下的50分。

设$\sigma$为$f$的集合占位幂级数,为了优化,我们应该直接考虑$\sigma$的递推式。

$${W_S}^p\sigma_{S,i}=\sum_{U\cup V=S\\j+|V|=i}\sigma_{U,j}g_V{W_V}^p$$

从小到大枚举i,依次确定$\sigma_{*,i}(i=1,2,3,\ldots)$。对于确定的i,枚举j,然后把$\sum_{S}\sigma_{S,j}$和$\sum_{|S|=i-j}g_S{W_S}^p$做一个子集卷积就可以了(注意不是子集卷积)。

vfk的论文里面把新增的未知数z的多项式作为了x的系数,现在这么做就有点像是把x的多项式作为了z的系数。

可是这样为什么就能优化呢?枚举i,枚举j,再做子集并卷积似乎还是$O(n^32^n)$的,但是注意到我们可以把$\sum_{S}\sigma_{S,j}$,$\sum_{|S|=j}g_S{W_S}^p$的FWT预先处理出来,对每个j,点值对应乘起来之后先不要FWT回去,而是对所有的j,把算出来的点值加起来,最后在FWT回去,这样卷起来那一步就是$O(2^n)$的。

可是说到底为什么这样会快呢?可能是因为我们直接从$\sigma$的递推式上面入手,而不是直接僵硬地使用子集卷积,所以挖掘到了更多的性质。

成功1A+成为loj上AC此题的第二个人+成为目前loj上代码最短的提交。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ele int
#define ll long long
using namespace std;
#define maxs (1<<21)
#define maxn 25
#define W 11
#define MOD 998244353
ele n,m,p,_cnt[1<<W],_log[maxs],w[maxn],pp[maxs],ipp[maxs],g[maxn],f[maxn][maxs],h[maxn][maxs],t1[maxs];
bool flag[maxs],cc[maxs];
inline ele getv(ele x,ele i){
	return (x>>i)&1;
}
inline ele setv(ele&x,ele i,ele k){
	x=x&~(1<<i);
	x=x|(k<<i);
	return x;
}
inline ele pw(ele a,ele x){
	ele ans=1,tmp=a%MOD;
	for (; x; x>>=1,tmp=(ll)tmp*tmp%MOD)
		if (x&1) ans=(ll)ans*tmp%MOD;
	return ans;
}
inline ele getcnt(ele x){
	ele ans=0;
	while (x){
		ans+=_cnt[x&((1<<W)-1)];
		x>>=W;
	}
	return ans;
}
void dfs(ele i,ele&s){
	setv(s,i,0);
	ele tmp=g[i]&s;
	for (int j=tmp&(-tmp); tmp; tmp-=j,j=tmp&(-tmp)){
		ele k=_log[j];
		if (getv(s,k)) dfs(k,s);
	}
}
inline void FWT(ele K,ele n,ele *a,ele *y){
	static ele f[maxs];
	f[0]=0; y[0]=a[0];
	for (int i=1; i<n; ++i){
		f[i]=f[i>>1]>>1;
		if (i&1) f[i]+=n>>1;
		y[i]=a[f[i]];
	}
	for (int p=1; p<n; p<<=1)
		for (int i=0; i<n; i+=(p<<1))
			for (int j=i; j<i+p; ++j)
				(y[j+p]+=(~K)?y[j]:(MOD-y[j]))%=MOD;
}
int main(){
	scanf("%d%d%d",&n,&m,&p);
	_cnt[0]=0;
	for (int i=1; i<(1<<W); ++i) _cnt[i]=_cnt[i>>1]+(i&1);
	_log[1]=0;
	for (int i=2; i<(1<<n); ++i) _log[i]=_log[i>>1]+1;
	memset(g,0,sizeof(g));
	for (int i=0; i<m; ++i){
		ele x,y;
		scanf("%d%d",&x,&y); --x,--y;
		setv(g[x],y,1); setv(g[y],x,1);
	}
	for (int i=0; i<n; ++i) scanf("%d",w+i);
	pp[0]=0;
	for (int i=1; i<(1<<n); ++i){
		ele j=i&(-i);
		pp[i]=(pp[i-j]+w[_log[j]])%MOD;
		ipp[i]=pw(pp[i],MOD-2);
	}
	flag[0]=false; cc[0]=true;
	for (int i=1; i<(1<<n); ++i){
		ele tmp=i,cnt=0;
		for (int j=tmp&(-tmp); tmp; tmp-=j,j=tmp&(-tmp)){
			ele k=_log[j];
			if (getcnt(g[k]&i)&1) ++cnt;
		}
		flag[i]=(cnt>0);
		ele s=i;
		dfs(_log[i&(-i)],s);
		cc[i]=!s;
	}
	memset(h,0,sizeof(h));
	for (int i=0; i<=n; ++i)
		for (int s=0; s<(1<<n); ++s)
			if (getcnt(s)==i && (flag[s] || !cc[s])) h[i][s]+=pw(pp[s],p);
	for (int i=0; i<=n; ++i){
		FWT(1,1<<n,h[i],t1);
		memcpy(h[i],t1,sizeof(t1));
	}
	memset(f,0,sizeof(f)); memset(t1,0,sizeof(t1));
	t1[0]=1; FWT(1,1<<n,t1,f[0]);
	ele ans=0;
	for (int i=1; i<=n; ++i){
		for (int j=0; j<=i; ++j)
			for (int s=0; s<(1<<n); ++s)
				(f[i][s]+=(ll)f[j][s]*h[i-j][s]%MOD)%=MOD;
		FWT(-1,1<<n,f[i],t1);
		for (int i=0; i<(1<<n); ++i) t1[i]=(ll)t1[i]*pw(ipp[i],p)%MOD;
		(ans+=t1[(1<<n)-1])%=MOD;
		FWT(1,1<<n,t1,f[i]);
	}
	printf("%d\n",ans);
	return 0;
}