Descripiton ![[WC2018]州区划分](https://img.it610.com/image/info8/6b7982262ec240ebb69dee5094c148b2.jpg)
文章图片
Solution 有一个比较显然的子集 \(DP\)
设 \(f[s]\) 表示集合状态为 \(s\) 的所有划分方案的满意度之和
\(f[s]=\sum_{t∈s}f[t]*g[s⊕t]\)
其中 \(g[s]\) 为集合 \(s\) 的人口数之和 .
这个东西用 \(FMT\) 求一下就行了.
由于这个题元素不能有交 , 所以我们需要多定义一维表示 \(1\) 的个数 .
然后用 \(FMT\) 做 \(n\) 轮 , 每一轮清空与 \(1\) 个数量不相符的状态.
复杂度 \(O(2^n*n^2)\)
#include
using namespace std;
templatevoid gi(T &x){
int f;
char c;
for(f=1,c=getchar();
c<'0'||c>'9';
c=getchar())if(c=='-')f=-1;
for(x=0;
c<='9'&&c>='0';
c=getchar())x=x*10+(c&15);
x*=f;
}
const int N=22,M=1010,mod=998244353;
inline int qm(int x,int k){
int sum=1;
for(;
k;
k>>=1,x=1ll*x*x%mod)if(k&1)sum=1ll*sum*x%mod;
return sum;
}
int n,m,P,b[N],head[N],nxt[M],to[M],num=0,w[N],in[N],f[N][1<<21],id[1<<21];
bool vis[N];
int d[1<<21],inv[1<<21],v[1<<21],c[1<<21],g[N][1<<21];
inline void link(int x,int y){nxt[++num]=head[x];
to[num]=y;
head[x]=num;
}
queueQ;
inline bool solve(int S){
for(int i=0;
i>i&1)v[S]+=w[i];
}
Q.push(id[S&(-S)]);
vis[id[S&(-S)]]=1;
int cnt=1;
while(!Q.empty()){
int x=Q.front(),u;
Q.pop();
for(int i=head[x];
i;
i=nxt[i]){
if(!(S>>to[i]&1))continue;
in[x]++;
if(!vis[u=to[i]])vis[u]=1,Q.push(u),cnt++;
}
}
if(cnt>i&1 && in[i]&1)return 1;
return 0;
}
inline void FMT(int *A,int o){
for(int j=1;
j>n>>m>>P;
b[0]=1;
for(int i=1;
i<=m;
i++)gi(x),gi(y),link(--x,--y),link(y,x);
for(int i=1;
i<=n;
i++)gi(w[i-1]),b[i]=b[i-1]<<1,id[1<<(i-1)]=i-1;
for(int i=1;
i 【[WC2018]州区划分】转载于:https://www.cnblogs.com/Yuzao/p/9245852.html
