题解 | #简单环#

//动态规划数组依旧是：dp[state][j];i表示状态，j表示在当前状态下的结尾节点。
//但不同的在于这道题要找简单环，而对于找简单环来说定起点和终点是比较重要的。
//因为只有知道了起点和终点，然后又知道起点和终点是否有一条直接的线连接，就证明是不是环。
//如果我们单纯的去执行状态转移方程的话，将种类数设为值确实可以得到在某个状态i下，以j结尾的方式数。
//但我们不知道起点在哪里。
//但在这里，我们可以保证下一个点一定在最小的那个1，也就是以最小的1位为起点前面。
//这样只要某个状态下，某个点结尾成立，那么它的起点就一定是最小下标的那一1。
//而对于判断环路来说有一个起点和终点就够了，所以绝对成立。
//但由于在某个环路上会顺时针和逆时针走两遍，所以最后结果要除2。
//又因为结果要取模，所以要用到费马小定理求逆元。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 22;
int mod = 998244353;
int dp[1<<20][maxn];
int mp[maxn][maxn];
int ans[maxn];

int binpow(int a, int n) {
	int res = 1;
	while (n) {
		if (n & 1) res = (res*a)%mod;
		a = (a*a)%mod;
		n>>=1;
	}
	return res;
}

signed main() 
{
	int n, m, k, s;
	int x, y;
	cin>>n>>m>>k;
	for (int i=1;i<=m;i++)
	{
		cin>>x>>y;
		mp[x][y] = 1;
		mp[y][x] = 1;
	}
	//将所有只有一个的初始设为1
	for (int i=0;i<n;i++)
	{
		dp[1<<i][i+1] = 1;
	}
	for (int state=1;state<=((1<<n)-1);state++)
	{
		//找到最低位的1，将他作为起点，一方面状态转移，一方面判断回路。
		for (int i=0;i<n;i++) {
			if ((state>>i)&1)
			{
				s = i+1;
				break;
			}
		}
		//枚举起点，也是判断回路的终点。
		for (int i=1;i<=n;i++)
		{
			if (((state>>(i-1))&1)==0) continue;
			for (int j=s+1;j<=n;j++)
			{
				if (((state>>(j-1))&1)==1) continue;
				int next_state = state|(1<<(j-1));
				if (mp[i][j])
					dp[next_state][j] = (dp[next_state][j]%mod+dp[state][i]%mod)%mod;
//					cout<<"dp="<<dp[next_state][j]<<endl;
			}
			//寻找回路。
			if (mp[i][s])
			{
				int len = __builtin_popcountll(state);
				if (len>2)
				{
					int pos = len%k+1;
					ans[pos] = (ans[pos]+dp[state][i]%mod)%mod;
//					cout<<"ans="<<ans[pos]<<endl;
				}
			}
		} 
	}
	for (int i=1;i<=k;i++)
	{
		cout<<(ans[i]*binpow(2, mod-2))%mod<<"\n";
	}
}