锐客网

  1. 首页 > it技术 > >

WC2018|WC2018 州区划分

WC2018州区划分

题目描述：
luogu
题解：
设$f[S]$表示选集合$S$时所有满意度乘积之和，$W[S]$表示集合$S$中选中的$w$之和。显然有这样一个式子：$$f[S]= \frac{1}{W[S]^p} \sum\limits_{T \subseteq S}f[T]*W[S-T]^p*[check(S-T)]$$
后面$check$的意思是判断$S-T$是否合法。
原题义中不合法的条件是存在一条欧拉回路。那么：

  • 若图不连通则不存在。
  • 若一个点的度数是奇数则不存在
  • 单个点一定存在
这样可以$O(2^nn^2)$处理出$check$。然后就是子集卷积了。
时间复杂度$O(2^nn^2)$。
代码：
WC2018|WC2018 州区划分
文章图片
WC2018|WC2018 州区划分
文章图片
#include #include #include using namespace std; typedef long long ll; const int N = 25; const int M = (1<<21)+20; const int MOD = 998244353; template inline void read(T&x) { T f = 1,c = 0; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){c=c*10+ch-'0'; ch=getchar(); } x = f*c; } templateinline void Mod(T&x){if(x>=MOD)x-=MOD; } int fastpow(int x,int y) { int ret = 1; while(y) { if(y&1)ret=1ll*ret*x%MOD; x=1ll*x*x%MOD; y>>=1; } return ret; } int inv(int x){return fastpow(x,MOD-2); } int n,m,p,mp[N],lg[M],cnt[M],w[N],W[M],Wp[M],iWp[M],f[N][M],g[N][M],h[M]; void fwt(int*a,const int len,const int k) { for(int i=1; i>1]+1; for(int i=1; i<(1<>j)&1)?(mp[j]&i):0; for(int j=0; j>j)&1)if(cnt[d[j]]&1)FG=1; for(int j=0; j>j)&1)if(findff(j)!=findff(x))FG=1; if(cnt[i]==1)FG = 0; Mod(W[i] = W[i-(i&-i)]+w[lg[i&-i]]),Wp[i]=fastpow(W[i],p); iWp[i] = inv(Wp[i]); if(FG)g[cnt[i]][i] = Wp[i]; } f[0][0] = 1; int len = (1<
View Code
【WC2018|WC2018 州区划分】转载于:https://www.cnblogs.com/LiGuanlin1124/p/11173951.html

    推荐阅读


      上一篇：调试STM32时遇到hardfault 的一些感悟

      下一篇：LaTex公式在线转图片