【WC2018】州区划分

Source and Judge

uoj348

Record

5h

Analysis

请先思考后再展开

先预处理好每一种方案(用二进制表示)的可行性、总人口
然后跑一个无限背包,因为是子集卷积,用fwt优化(有教程,第一维是二进制下1数量)
$f(p1,k) \times sum^p(k)=\sum_{i|j=k} f(p2,i) okay(p1-p2,j) sum^p(j)$
枚举p1和p2来做或运算卷积,然后把非法状态去掉,还要把讨厌的系数去掉
时间复杂度 $O(n^2 2^n)$

友情提示:判断合法性,记得要判断联通块数量……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
//Zory-2018
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
#define pr pair<double,int>
#define FR first
#define SE second
#define MP make_pair
const int MAX_N=24;
const int MOD=998244353;
const int MAX_S=(1<<22)+10;
int qpower(int x,int e)
{
if(e==0) return 1;
if(e==1) return x;
return (ll)x*x%MOD;
}
int bin[40],pp[MAX_S],inv[MAX_S];
int n,m,p;
void FWT(int A[],int f)
{
for(int i=0;i<n;i++)
for(int j=bin[n]-1;j>=0;j--)
if(j&bin[i]) (A[j]+=A[j^bin[i]]*f)%=MOD;
}
int sum[MAX_S];
struct Edge{int x,y;}e[MAX_N*MAX_N];
int deg[MAX_N],fa[MAX_N];
int findfa(int x) {return fa[x]=(fa[x]==x?x:findfa(fa[x]));}
bool check(int s)//是否存在欧拉回路
{
for(int i=0;i<n;i++) fa[i]=i,deg[i]=0;
for(int i=1;i<=m;i++) if(s&bin[e[i].x] and s&bin[e[i].y])
{
deg[e[i].x]^=1,deg[e[i].y]^=1;
int fx=findfa(e[i].x),fy=findfa(e[i].y);
if(fx!=fy) fa[fx]=fy;
}
int t1=0,t2=0;for(int i=0;i<n;i++) if(s&bin[i]) t1+=deg[i],t2+=(i==findfa(i));
return t1==0 and t2==1;//记得判联通块数量
}
int A[MAX_N][MAX_S],f[MAX_N][MAX_S],tmp[MAX_S];
void main()
{
bin[0]=1;for(int i=1;i<=30;i++) bin[i]=bin[i-1]<<1;
pp[0]=0;for(int i=1;i<MAX_S;i++) pp[i]=pp[i>>1]+(i&1);
inv[0]=inv[1]=1;for(int i=2;i<MAX_S;i++) inv[i]=ll(MOD-MOD/i)*inv[MOD%i]%MOD;
scanf("%d%d%d",&n,&m,&p);
for(int i=1;i<=m;i++) scanf("%d%d",&e[i].x,&e[i].y),e[i].x--,e[i].y--;
for(int i=0;i<n;i++) scanf("%d",&sum[bin[i]]);
for(int i=0;i<bin[n];i++) sum[i]=sum[i^(i&-i)]+sum[i&-i];
for(int i=1;i<bin[n];i++) {sum[i]=qpower(sum[i],p);if(check(i)==0) A[pp[i]][i]=sum[i];}
for(int i=1;i<=n;i++) FWT(A[i],1);
f[0][0]=1;FWT(f[0],1);
for(int p1=1;p1<=n;p1++)
{
for(int p2=0;p2<p1;p2++)
for(int i=0;i<bin[n];i++)
(f[p1][i]+=(ll)f[p2][i]*A[p1-p2][i]%MOD)%=MOD;
FWT(f[p1],-1);
for(int i=0;i<bin[n];i++) f[p1][i]=(ll)f[p1][i]*inv[sum[i]]%MOD;
FWT(f[p1],1);
}
FWT(f[n],-1);
printf("%d",(f[n][bin[n]-1]+MOD)%MOD);
}
};
int main()
{
srand(time(0));
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/f65b.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%