锐客网

  1. 首页 > it技术 > >

c++|loj2340 WC2018 州区划分 状压dp+FWT

c++状压DPfwt

Description 题面到处都有系列。。
Solution FMT是啥，能吃吗
首先考虑怎么判合法子图（也就是欧拉回路），我们n2*2n枚举点然后统计度数就可以了
那么一个比较显然的dp就是设f[S]表示二进制状态为S的所有答案,g[S]表示S这个集合分成一份的贡献
我们枚举S的子集转移即可，这样做是O(3n)的
【c++|loj2340 WC2018 州区划分 状压dp+FWT】考虑把柿子写出来，那么就是 f S = ∑ T ? S f T ? g S ? T f_{S}=\sum\limits_{T\subset S}f_{T}\cdot g_{S\setminus T} fS?=T?S∑?fT??gS?T?
这实际上就是一个子集卷积，只不过这个有自己卷自己的部分。
注意到 ∑ T ? S f T ? g S ? T = ∑ U ? S , V ? S , U ∪ V = S , U ∩ V = ? f U ? g V = ∑ U ? S , V ? S , ∣ U ∣ + ∣ V ∣ = ∣ S ∣ , U ∪ V = S f U ? g V \sum\limits_{T\subset S}{f_{T}\cdot g_{S\setminus T}}=\sum\limits_{U\subset S,V\subset S,U\cup V=S,U\cap V=\emptyset}{f_{U}\cdot g_{V}}=\sum\limits_{U\subset S,V\subset S,|U|+|V|=|S|,U\cup V=S}f_{U}\cdot g_{V} T?S∑?fT??gS?T?=U?S,V?S,U∪V=S,U∩V=?∑?fU??gV?=U?S,V?S,∣U∣+∣V∣=∣S∣,U∪V=S∑?fU??gV?
这里的转化十分的巧妙
于是我们设 f i , S f_{i,S} fi,S?表示二进制中i位是1，状态为S的答案，我们对i做卷积，然后对S做或卷积就可以了
于是复杂度就是 O ( n 2 ? 2 n ) O(n^2\cdot2^n) O(n2?2n)的了，我写的代码要卡一卡常数。。
Code

#include #include #include #define rep(i,st,ed) for (register int i=st; i<=ed; ++i)typedef long long LL; const int MOD=998244353; const int N=2197152; LL f[22][N],g[22][N],s[N],inv[N]; int rc[22][22],fa[22],d[22],w[22],c[N]; int n,m,p,lim; void upd(LL &x,LL y) { x+=y; (x>=MOD)?(x-=MOD):0; }int read() { int x=0,v=1; char ch=getchar(); for (; ch<'0'||ch>'9'; v=(ch=='-')?(-1):(v),ch=getchar()); for (; ch<='9'&&ch>='0'; x=x*10+ch-'0',ch=getchar()); return x*v; }void FWT(LL *a,int f) { for (register int i=1; i>=1) { (dep&1)?(res=res*x%MOD):0; x=x*x%MOD; } return res; }int find(int x) { return !fa[x]?x:(fa[x]=find(fa[x])); }bool merge(int x,int y) { x=find(x),y=find(y); if (x==y) return false; return 1|(fa[x]=y); }bool check(int S) { rep(i,1,n) fa[i]=d[i]=0; int cnt=1; rep(i,1,n) if (S>>(i-1)&1) { s[S]=(s[S]+w[i])%MOD; rep(j,i+1,n) if (S>>(j-1)&1) { if (!rc[i][j]) continue; ++d[i],++d[j]; cnt+=merge(i,j); } } inv[S]=ksm(ksm(s[S],MOD-2),p); rep(i,1,n) if (S>>(i-1)&1) { if (d[i]&1) return false; cnt--; } return !cnt; }int main(void) { freopen("data.in","r",stdin); freopen("myp.out","w",stdout); n=read(),m=read(),p=read(); lim=(1<>1]+(i&1); rep(i,1,lim) if (!check(i)) { // printf("%d\n", i); g[c[i]][i]=ksm(s[i],p); } f[0][0]=1; rep(i,0,n-1) f[1][1<

    推荐阅读


    上一篇：《使命感就是超能力》day2复盘

    下一篇：Nginx error_page 自定义错误页面设置