简单环 题解

前面部分跟“郊区春游”差不多，属于TSP问题，不懂的可以看一下我郊区春游的那篇题解。
也是枚举起点、终点（终点这里得比起点大，避免重复统计），进行状态转移，不同的是这里的dp数组记录的是方案数量，然后每次转移以后要判终点和起点是否可以相连，相连就进行统计。
最后答案要除以2，原因是大于等于3的回路可能会顺时针走一遍、逆时针走一遍（本题只统计大于等于3的就是这个原因）。
除以2用逆元来解决在模意义下的除法。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lowbit(x) x&(-x)
const ll mod=998244353;
int lowpoint(int x)
{
    int ans=1;
    while(!(x&1))
    {
        x>>=1;
        ans++;
    }
    return ans;
}
int n,m,K;
const int N=22;
int mp[N][N];
ll ans[N];
ll dp[1<<22][22];
int main()
{
    scanf("%d%d%d",&n,&m,&K);
    while(m--)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        mp[u][v]=mp[v][u]=true;
    }
    for(int i=1;i<=n;i++) //枚举那些边是起点
    {
        dp[1<<(i-1)][i]=1;
    }
    int len=(1<<n)-1;//最后一个状态，即所有点都走过
    for(int i=1;i<=len;i++)
    {
        int s;
        for(int j=1;j<=n;j++)
            if((i>>(j-1))&1){
                s=j;
                break;
            }
        for(int j=1;j<=n;j++) //枚举起点
        {
            int jj=1<<(j-1);
            if(!(i&jj)) continue;
            for(int k=s+1;k<=n;k++)//枚举终点
            {
                int kk=1<<(k-1);
                if(i&kk) continue;
                if(mp[j][k])
                {
                    dp[i|kk][k]=(dp[i|kk][k]+dp[i][j])%mod;
                }
            }
            if(mp[j][s])
            {
                int len=__builtin_popcount(i);
                if(len>=3)
                    ans[len%K]=(ans[len%K]+dp[i][j])%mod;
            }
        }
    }
    for(int i=0;i<K;i++)
        printf("%lld\n",(ans[i]*(mod+1)/2)%mod);
}