刷题记录:牛客NC16544简单环

传送门:牛客

题目描述:

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

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

主要思路;

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

$dp[S|(1<<v)][v]=(dp[S][u]+dp[S|(1<<v)][v])$

注意此时需要累加,而不是直接进行转移,为什么呢,因为我们的这条链只是确定了起点和末尾所以我们的这条链并不是确定的,所以我们的需要进行的是累加.

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

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

$\_\_builtin\_popcount()$,这个库函数是用来求出一个数的二进制位中1的数量(复杂度应该是$O(1)$的,使用查表法做的)

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

下面是具体的代码部分:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
#include <deque>
using 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;i<n;i++) dp[1<<i][i]=1;
	for(int S=1;S<(1<<n);S++) {
		int start=-1;
		for(int j=0;j<n;j++) {
			if((S>>j)&1) {
				start=j;
				break;
			}
		}
		for(int u=0;u<n;u++) {
			if(!((S>>u)&1)) continue;
			if(dp[S][u]==0) continue;
			for(int v=start+1;v<n;v++) {
				if((S>>v)&1) continue;
				if(!mp[u][v]) continue;
				dp[S|(1<<v)][v]=(dp[S][u]+dp[S|(1<<v)][v])%mod;
			}
			if(mp[u][start]) {
				if(__builtin_popcount(S)<3) continue;
				res[__builtin_popcount(S)%k]=(res[__builtin_popcount(S)%k]+dp[S][u])%mod;
			}
		}
	}
	for(int i=0;i<k;i++) {
		cout<<(res[i]*qpow(2,mod-2))%mod<<endl;
	}
	return 0;
}