网站建设全教程,公司创建一个网站需要多少钱,crm管理系统 一般包含,上海网站建设平台站霸网络题目传送门
引
属于一眼题,不看时间限制 8 s 8s 8s 容易被诈骗
解法
简单容斥 大概 式子就是 ∑ ( − 1 ) M ∗ K ∣ S ∣ \sum(-1)^{M}*K^{|S|} ∑(−1)M∗K∣S∣ , M M M 为边集的大小#xff0c; ∣ S ∣ |S| ∣S∣ 为联通块的数量 那么我们就有 空间复杂度#…题目传送门
引
属于一眼题,不看时间限制 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 iostreamusing db double;
using ll long long;
using namespace std;const int N37,mod998244353;int n,m,k,p[N],u[N],v[N],fa[N];int find(int x) { return xfa[x]?x:find(fa[x]); }int dfs(int i,int cnt) {if(im1) return p[cnt];int xfind(u[i]),yfind(v[i]);if(xy) return 0;int f1dfs(i1,cnt);fa[y]x;int f2dfs(i1,cnt-1);fa[y]y;return (f1-f2mod)%mod;
}
int main(){srand(998244353);scanf(%d%d%d,n,m,k);p[0]1; for(int i1;in;i) p[i]1ll*p[i-1]*k%mod,fa[i]i;for(int i1;im;i) {scanf(%d%d,u[i],v[i]);if(rand()%2) swap(u[i],v[i]);}printf(%d\n,dfs(1,n));
}结
其实就是想记录一下优化的方法
