题目链接：https://www.nowcoder.com/acm/contest/114/C
解题思路：状态压缩DP，把环拆成一条路径，设dp[i][s]表示当前路径中点的状态为ｓ，且当前路径的末尾为ｉ的方案数。为了使路径不重不漏，每次枚举一个编号最小的点ｖ作为起点，这样计算时因为一个环有两种拆成路径的方法，所以答案要除以2
#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <cmath> #include <map> #include <set> #include <stack> #include <queue> #include <vector> #include <bitset> #include <functional> using namespace std; #define LL long long const int INF = 0x3f3f3f3f; const int mod = 998244353; int dp[25][1 << 22]; int ans[25]; int x[25][25]; int a[25], b[25], cnt1, cnt2; int n, m, k, u, v; int main() { while (~scanf("%d%d%d", &n, &m, &k)) { for (int i = 1; i <= m; i++) { scanf("%d %d", &u, &v); u--; v--; x[u][v] = x[v][u] = 1; } for (int i = 0; i < n; i++) dp[i][1 << i] = 1; for (int i = 1; i < (1 << n); i++) { cnt1 = cnt2 = 0; for (int j = 0; j < n; j++) { if (i & (1 << j)) a[cnt1++] = j; else if (cnt1) b[cnt2++] = j; } for (int j = 0; j < cnt1; j++) { if (x[a[0]][a[j]] && cnt1 > 2) (ans[cnt1 % k] += dp[a[j]][i]) %= mod; for (int p = 0; p < cnt2; p++) { if (x[a[j]][b[p]]) (dp[b[p]][i | (1 << b[p])] += dp[a[j]][i]) %= mod; } } } for (int i = 0; i < k; i++) printf("%d\n", 1LL * ans[i] * 499122177 % mod); } return 0; }