[WC2018]州区划分

2024-03-16 23:32

文章标签 划分州区 wc2018

本文主要是介绍[WC2018]州区划分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

州区划分

题解

~~挺水的题呀。~~

要求的是 $\sum ( \prod_{i=1}^{k} \frac{ \sum_{x \in V_{i}}w_{x}}{ \sum_{j=1}^{i} \sum_{x\in V_{j}}w_{x}})^p \, mod \, 998244353$ ，需要保证 $V_{i}$ 中不存在欧拉回路。

对于判欧拉回路，可以通过状压，求出 $S$ 以内所有图的状态的是否为欧拉回路。

很容易想到dp，设 $f_{s}$ 为集合 $s$ 的答案， $g_{s}$ 表示集合 $s$ 是否合法。于是乎，可以得到：

$f_{s}= \sum_{t\in s}f_{s-t}g_{t}\left(\frac{val_{t}}{val_{s}} \right )^p$ ， $val_{s}$ 是集合s的的人口数，也就是所有包含的 $w$ 的和。

枚举子集明显是 $O\left(3^n \right )$ ，由于 $n\leq 21$ ，明显会T。

于是我们可以将其卷积，变成了

$f_{s}= \sum_{a\cap b= \o ,a\cup b= s}f_{a}g_{b}\left(\frac{val_{b}}{val_{s}} \right )^p$ ，很明显的一个卷积，可以将后面那一块加入 $g_{b}$ 中。

我们的式子变为 $f_{i,s}g_{i,s}= \sum_{j=0}^{i-1}\sum_{t\in s}f_{j,s-t}g_{i-j,t}$ ，通过FMT可以求出任意的 $f_{i,s}g_{i,s}$ ，再将 $g_{i,s}$ 除掉就可以得到 $f_{i,s}$ 了。

答案就是 $f_{n,S}$ 。

源码

代码太慢了，就加了一个超级优化。笔者~~又不是妹儿，加优化当然就不会T了~~

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN (1<<21)+5
#define reg register
typedef long long LL;
const int mo=998244353;
template<typename _T>
inline void read(_T &x){_T f=1;x=0;char s=getchar();while('0'>s||'9'<s){if(s=='-')f=-1;s=getchar();}while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}x*=f;
}
int n,m,p,pos[MAXN],e[22],w[MAXN],iw[MAXN],cnt[MAXN];
int f[22][MAXN],g[22][MAXN],nxt[MAXN];LL ans[MAXN];
inline int add(const int x,const int y){return x+y<mo?x+y:x+y-mo;}
inline int qkpow(int a,int s){int t=1;while(s){if(s&1)t=1ll*a*t%mo;a=1ll*a*a%mo;s>>=1;}return t;}
inline int inv(const int x){return x^1?mo-1ll*(mo/x)*inv(mo%x)%mo:1;}
inline void FWT(int *A,const int typ){for(reg int i=0;i<n;++i)for(reg int j=1;j<(1<<n);++j)if(j&(1<<i))A[j]=add(A[j],typ>0?A[j^(1<<i)]:mo-A[j^(1<<i)]);
}
signed main(){read(n);read(m);read(p);const int lim=(1<<n);for(reg int i=1;i<=n;++i)pos[1<<i-1]=i;for(reg int i=1;i<=m;++i){int u,v;read(u);read(v);e[u]|=(1<<v-1);e[v]|=(1<<u-1);}for(reg int i=0;i<n;++i)read(w[1<<i]);for(reg int i=1;i<lim;++i)nxt[i]=i&-i,cnt[i]=cnt[i^nxt[i]]+1;for(reg int j=1;j<lim;++j){w[j]=w[nxt[j]]+w[j^nxt[j]];int t=nxt[j];iw[j]=inv(qkpow(w[j],p));bool fg=0;for(reg int i=j;i;i^=nxt[i])if(cnt[e[pos[nxt[i]]]&j]&1){fg=1;break;}if(!fg)for(reg int i=nxt[j],k;i;)k=pos[nxt[i]],i^=nxt[i],i|=e[k]&j&~t,t|=e[k]&j;if(j==t&&!fg)continue;g[cnt[j]][j]=qkpow(w[j],p);}f[0][0]=1;FWT(f[0],1);int *a,*b;for(reg int i=1;i<=n;++i){FWT(g[i],1);for(int j=0;j<lim;j++)ans[j]=0;for(reg int j=0;j<i;++j){a=f[j];b=g[i-j];for(reg int k=0;k<lim;++k)ans[k]+=1ll*a[k]*b[k];}a=f[i];for(reg int j=0;j<lim;++j)a[j]=ans[j]%mo;FWT(a,-1);for(reg int j=0;j<lim;++j)a[j]=1ll*a[j]*iw[j]%mo;if(i<n)FWT(a,1);}printf("%d",f[n][lim-1]);return 0;
}