Solution 【FWT|[LOJ]#2340. 「WC2018」州区划分 FWT+欧拉回路】首先对于每个子集判断是否可以单独成一个州，也就是判断是否存在欧拉回路，存在欧拉回路当且仅当图连通且每个点的度数都为偶数。设 s u m S sum_S sumS?为集合 S S S所有元素 w w w之和，若 S S S能成一个州， g S = s u m S p g_S={sum_S}^p gS?=sumS?p，设 f S f_S fS?为集合 S S S所有划分方案的乘积之和，那么 f S = 1 s u m S p ∑ f T g S ? T , T &
( S ? T ) = 0 f_S={1\over {sum_S}^p}\sum f_{T}g_{S-T},T\&
(S-T)=0 fS?=sumS?p1?∑fT?gS?T?,T&(S?T)=0。这就是个子集卷积，不过会自己卷自己，要按照 1 1 1的个数分层转移。
不知道为什么，用异或卷积比用或卷积做慢了 10 s 10s 10s……
Code
#include
using namespace std;
#define LL long long
#define pa pair
const int inf=2147483647;
const int mod=998244353,inv=(mod+1)/2;
int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*f;
}
inline void upd(int&x,int y){x+=y;
if(x>=mod)x-=mod;
}
int Pow(int x,int y)
{
if(!y)return 1;
int t=Pow(x,y>>1),re=(LL)t*t%mod;
if(y&1)re=(LL)re*x%mod;
return re;
}
int n,m,p,w[22],f[22][1<<21],g[22][1<<21],s[1<<21],o[1<<21],invs[1<<21],deg[22];
vectorh[22];
int tS;
void dfs(int x,int S)
{
tS|=(1<<(x-1));
for(int i=0;
i=0;
j--)
if(j&(1<>1]+(i&1);
for(int i=1;
i<=m;
i++)
{
int x=read(),y=read();
h[x].push_back(y),h[y].push_back(x);
}
for(int i=1;
i<=n;
i++)w[i]=read();
for(int S=1;
S<(1<
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- FWT|【LOJ #2340】【WC 2018】—州区划分（子集卷积+状压dp）
- 状压dp|[WC2018]州区划分
- 模板|FWT 模板
- c++|loj2340 WC2018 州区划分 状压dp+FWT
- loj|[loj2340][FWT][子集卷积]州区划分