刷题记录:牛客NC16544简单环-创新互联

传送门:牛客

成都创新互联公司成立十多年来，这条路我们正越走越好，积累了技术与客户资源，形成了良好的口碑。为客户提供网站设计制作、网站设计、网站策划、网页设计、域名注册、网络营销、VI设计、网站改版、漏洞修补等服务。网站是否美观、功能强大、用户体验好、性价比高、打开快等等，这些对于网站建设都非常重要，成都创新互联公司通过对建站技术性的掌握、对创意设计的研究为客户提供一站式互联网解决方案，携手广大客户，共同发展进步。

题目描述:

给定一张n个点m条边的无向图，求出图中所有简单环的数量。(简单环：简单环又称简单回路，图的顶点序列中，除
了第一个顶点和最后一个顶点相同外，其余顶点不重复出现的回路叫简单回路。或者说，若通路或回路不重复地包含
相同的边，则它是简单的)
输入;
4 6 3
1 2
2 3
3 4
4 1
2 4
1 3
输出:
4
3
0

一道状压dp题.但是感觉还是挺难看出来的…

主要思路;

首先我们需要先将这道题往状压dp的那条思路上去想.然后我们就会想到可以这么做,就是用一个 d p [ S ] [ u ] dp[S][u] dp[S][u]来存储状态为S时(我们将每一个点是不是在链中用二进制表示形成一个集合S)终点为 u u u的链的数量(注意此时并不是环的数量).
为了不漏不重复,我们可以将每一个状态的第一个1当做我们的起点位置 k k k,将最后的 u u u当做我们的终点位置,然后对于我们的这条链,显然我们可以用 u u u的邻接点 v v v来进行转移,这里的转移依据是,既然我们的开始位置 k k k到结束位置 u u u能够组成一条链,那么我们的 k k k到 v v v显然也是可以组成一条链的,那么我们就可以进行转移了.

d p [ S ∣ ( 1 < < v ) ] [ v ] = ( d p [ S ] [ u ] + d p [ S ∣ ( 1 < < v ) ] [ v ] ) dp[S|(1<注意此时需要累加,而不是直接进行转移,为什么呢,因为我们的这条链只是确定了起点和末尾所以我们的这条链并不是确定的,所以我们的需要进行的是累加.

然后对于我们枚举的每一个状态(也就是每一条链),因为我们记录了链的开头和结尾,所以直接判断一下开头和结尾能不能链接即可(也就是这条链能不能组成一个环)

在下列代码中用到了一个比较偏的c++函数

_ _ b u i l t i n _ p o p c o u n t ( ) \_\_builtin\_popcount() __builtin_popcount(),这个库函数是用来求出一个数的二进制位中1的数量(复杂度应该是 O ( 1 ) O(1) O(1)的,使用查表法做的)

然后是一些比较琐细的问题,就是在之前的求的过程中,即使我们安排了顺序但是还是有重复的,因为对于一个环来说,即使我们确定了开头,但是由于顺逆时针的关系,会导致我们最后的答案是两倍的,所以我们需要除二,但是由于我们过程中用到了取模,所以我们并不能直接除2,所以需要乘法逆元,对于乘法逆元,如果不清楚的可以看我的这篇博客,对乘法进行了较为详细的解释和讲解

下面是具体的代码部分:

#include#include#include#include 
#include#include#include#include#include#include#includeusing namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define int long long 
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
const int mod=998244353;
int n,m,k;
ll qpow(ll a,ll b) {ll ans=1;
	while(b) {if(b&1) ans=(ans*a)%mod;
		b>>=1;
		a=(a*a)%mod;
	}
	return ans;
}
int mp[30][30],dp[1<<21][30];int res[30];
signed main() {n=read();m=read();k=read();
	int u,v;
	for(int i=1;i<=m;i++) {u=read();v=read();
		mp[--u][--v]=1;mp[v][u]=1;
	}
	for(int i=0;iint start=-1;
		for(int j=0;j	if((S>>j)&1) {		start=j;
				break;
			}
		}
		for(int u=0;u	if(!((S>>u)&1)) continue;
			if(dp[S][u]==0) continue;
			for(int v=start+1;v		if((S>>v)&1) continue;
				if(!mp[u][v]) continue;
				dp[S|(1<		if(__builtin_popcount(S)<3) continue;
				res[__builtin_popcount(S)%k]=(res[__builtin_popcount(S)%k]+dp[S][u])%mod;
			}
		}
	}
	for(int i=0;icout<<(res[i]*qpow(2,mod-2))%mod<


                
     你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
                

                当前名称：刷题记录:牛客NC16544简单环-创新互联                

                本文网址：http://wjwzjz.com/article/gcojj.html

新网创想网站建设，新征程启航

刷题记录:牛客NC16544简单环-创新互联

其他资讯