[ABC294Ex] K-Coloring
题目传送门
引
属于一眼题,不看时间限制 8 s 8s 8s 容易被诈骗
解法
简单容斥
大概 式子就是 ∑ ( − 1 ) M ∗ K ∣ S ∣ \sum(-1)^{M}*K^{|S|} ∑(−1)M∗K∣S∣ , M M M 为边集的大小， ∣ S ∣ |S| ∣S∣ 为联通块的数量
那么我们就有 空间复杂度： O ( 2 N ) = 1 e 9 O(2^N) =1e9 O(2N)=1e9 ,时间复杂度： O ( 2 N M ) O(2^NM) O(2NM)
1.用 d f s dfs dfs 搜索所有的状态，可以省去开数组的空间
2.加上剪枝,当加入一条边后,图的连通性未改变，那么后继所有状态一定都会相互抵消,直接返回 0 0 0
加上两种优化后
空间复杂度： O ( 1 ) O(1) O(1)
时间复杂度： O ( 2 N ∗ 玄学 ) O(2^{N}*玄学) O(2N∗玄学)
Code
#include <algorithm>
#include <iostream>using db = double;
using ll = long long;
using namespace std;const int N=37,mod=998244353;int n,m,k,p[N],u[N],v[N],fa[N];int find(int x) { return x==fa[x]?x:find(fa[x]); }int dfs(int i,int cnt) {if(i==m+1) return p[cnt];int x=find(u[i]),y=find(v[i]);if(x==y) return 0;int f1=dfs(i+1,cnt);fa[y]=x;int f2=dfs(i+1,cnt-1);fa[y]=y;return (f1-f2+mod)%mod;
}
int main(){srand(998244353);scanf("%d%d%d",&n,&m,&k);p[0]=1; for(int i=1;i<=n;i++) p[i]=1ll*p[i-1]*k%mod,fa[i]=i;for(int i=1;i<=m;i++) {scanf("%d%d",&u[i],&v[i]);if(rand()%2) swap(u[i],v[i]);}printf("%d\n",dfs(1,n));
}
结
其实就是想记录一下优化的方法