锐客网

  1. 首页 > it技术 > >

好题集|UOJ348 WC2018 州区划分

bzojUOJ多项式好题集

Problem UOJ
Solution 做的时候SB了，纠结了好久怎么判定欧拉回路，YY了半天状压DP无果，后来突然想起欧拉回路的充要条件是联通且点的度数为偶数。
设 h [ s ] = ∑ x ∈ s w x h[s]=\sum_{x\in s} w_x h[s]=∑x∈s?wx?，如果 s s s是合法的那么 g [ s ] = h [ s ] g[s]=h[s] g[s]=h[s]，否则 g [ s ] = 0 g[s]=0 g[s]=0
那么枚举最后的划分出来的子集
f [ s ] = 1 h [ s ] k ∑ t ? s g [ t ] k × f [ s ? t ] f[s]=\frac 1 {h[s]^k}\sum_{t\subseteq s} g[t]^k \times f[s-t] f[s]=h[s]k1?t?s∑?g[t]k×f[s?t]
这个就是一个子集卷积。子集卷积有一个 O ( n 2 2 n ) O(n^22^n) O(n22n)的方法，就是按元素个数从小到大计算 f [ S ] f[S] f[S]。在计算 f [ S ] f[S] f[S]的时候，使有 j j j个元素的 g g g和有 i ? j i-j i?j个元素的 f f f做一次或卷积，为了限定两个集合无交集，卷积后如果元素个数小于 i i i个，我们就去掉它的贡献。
【好题集|UOJ348 WC2018 州区划分】时间复杂度 O ( n 2 2 n ) O(n^22^n) O(n22n)，空间复杂度 O ( n 2 n ) O(n2^n) O(n2n)。
Code

#include #define lowbit(x) ((x)&(-(x))) using namespace std; typedef long long ll; const int maxn=2100000,mod=998244353; template inline int getmin(Tp &x,Tp y){return y inline int getmax(Tp &x,Tp y){return y>x?x=y,1:0; } template inline void read(Tp &x) { x=0; int f=0; char ch=getchar(); while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); if(ch=='-') f=1,ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); if(f) x=-x; } int n,m,p,N,w[25],e[25][25],fa[25],cnt[maxn],lg[maxn]; int f[22][maxn],g[22][maxn],ig[maxn]; int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]); } int merge(int x,int y) { int fx=find(x),fy=find(y); if(fx==fy) return 0; return fa[fy]=fx; } int pls(int x,int y){return x+y>=mod?x+y-mod:x+y; } int dec(int x,int y){return x-y<0?x-y+mod:x-y; } int power(int x,int y) { int res=1; for(; y; y>>=1,x=(ll)x*x%mod) if(y&1) res=(ll)res*x%mod; return res; } int check(int s) { static int top,tot,stk[25],d[25]; if(cnt[s]==1) return 0; top=0; for(; s; s-=lowbit(s)) stk[++top]=lg[lowbit(s)],d[top]=0,fa[top]=top; tot=top; for(int i=1; i<=top; i++) for(int j=1; j1) return 1; for(int i=1; i<=top; i++) if(d[i]&1) return 1; return 0; } void input() { int u,v; read(n); read(m); read(p); N=1<>1]+(i&1); if(cnt[i]>1) g[cnt[i]][i]=g[cnt[i]-1][i-lowbit(i)]+w[lg[lowbit(i)]]; } for(int i=1; i

    推荐阅读


    上一篇：七言｜春去·盼春

    下一篇：电子模块实验|看看那些来自电路造型挑战赛中的作品