Description
给定一张n个点m条边的无向图，一个点的导出子图是不合法的当且仅当其不连通，或者存在欧拉回路。
你现在需要把所有点划分成若干个点的导出子图，使得所有子图合法。
每个点有点权wi，一个导出子图的价值定义为其之中的点的w之和与其之前被选择的所有点的w之和之比的p次幂。一个划分方案的价值为所有子图的价值之积
求所有合法方案的价值之和。
n<=21
Solution
【状压dp|[WC2018]州区划分】首先3^n的子集Dp显然，我们有很多种办法把这个东西优化到2^n*n^2
讲一下吨吨吨的标算，设F[i][s]表示有i个城市，集合为s（可以重复）的答案。
显然答案最后就是F[n][2^n-1]，如果有重复达不到这个状态。
那么直接or卷积就好了。
为什么我的FWT和你们不一样
Code
#include
#include
#include
#define fo(i,a,b) for(int i=a;
i<=b;
i++)
#define fd(i,a,b) for(int i=a;
i>=b;
i--)
using namespace std;
typedef long long ll;
int read() {
char ch;
for(ch=getchar();
ch<'0'||ch>'9';
ch=getchar());
int x=ch-'0';
for(ch=getchar();
ch>='0'&&ch<='9';
ch=getchar()) x=x*10+ch-'0';
return x;
}const int N=25,S=(1<<21)+5,Mo=998244353;
int pwr(int x,int y) {
int z=1;
for(;
y;
y>>=1,x=(ll)x*x%Mo)
if (y&1) z=(ll)z*x%Mo;
return z;
}int n,m,p,x[N*N],y[N*N],fa[N],two[N],cnt[S],a[N],deg[N];
int f[N][S],g[N][S],sum[S],inv[S];
bool ok[S];
int get(int x) {return fa[x]?fa[x]=get(fa[x]):x;
}void merge(int x,int y) {
x=get(x);
y=get(y);
if (x==y) return;
fa[y]=x;
}void FWT(int *a,int l,int r) {
if (l==r) return;
int mid=l+r>>1;
FWT(a,l,mid);
FWT(a,mid+1,r);
int len=mid-l+1;
fo(i,l,mid) (a[i+len]+=a[i])%=Mo;
}void IFWT(int *a,int l,int r) {
if (l==r) return;
int mid=l+r>>1;
int len=mid-l+1;
fo(i,l,mid) (a[i+len]+=Mo-a[i])%=Mo;
IFWT(a,l,mid);
IFWT(a,mid+1,r);
}int main() {
n=read();
m=read();
p=read();
fo(i,1,m) x[i]=read(),y[i]=read();
fo(i,1,n) a[i]=read();
two[0]=1;
fo(i,1,n) two[i]=two[i-1]<<1;
fo(i,0,two[n]-1) cnt[i]=cnt[i>>1]+(i&1);
fo(s,0,two[n]-1) {
fo(i,1,n) if (two[i-1]&s) (sum[s]+=a[i])%=Mo;
sum[s]=pwr(sum[s],p);
inv[s]=pwr(sum[s],Mo-2);
fo(i,1,n) fa[i]=deg[i]=0;
fo(i,1,m) {
if (!(two[x[i]-1]&s)) continue;
if (!(two[y[i]-1]&s)) continue;
merge(x[i],y[i]);
deg[x[i]]++;
deg[y[i]]++;
}
int tmp=0,res=0;
fo(i,1,n) if (two[i-1]&s) tmp+=deg[i]&1;
fo(i,1,n) if (two[i-1]&s) res+=get(i)==i;
ok[s]=tmp||(res>1);
}
f[0][0]=1;
FWT(f[0],0,two[n]-1);
fo(s,0,two[n]-1)
if (ok[s]) g[cnt[s]][s]=sum[s];
fo(i,1,n) FWT(g[i],0,two[n]-1);
fo(i,1,n) {
fo(j,1,i)
fo(s,0,two[n]-1)
(f[i][s]+=(ll)f[i-j][s]*g[j][s]%Mo)%=Mo;
IFWT(f[i],0,two[n]-1);
fo(s,0,two[n]-1) f[i][s]=(ll)f[i][s]*inv[s]%Mo;
FWT(f[i],0,two[n]-1);
}
IFWT(f[n],0,two[n]-1);
printf("%d\n",f[n][two[n]-1]);
return 0;
} 推荐阅读
- 主席树|191101CSP模拟题解
- FWT|【LOJ #2340】【WC 2018】—州区划分（子集卷积+状压dp）
- 模板|FWT 模板
- bzoj1076: [SCOI2008]奖励关
- c++|loj2340 WC2018 州区划分 状压dp+FWT
- FWT|[LOJ]#2340. 「WC2018」州区划分 FWT+欧拉回路
- loj|[loj2340][FWT][子集卷积]州区划分