题解：AT_abc411_g [ABC411G] Count Cycles

· · 题解

更好的阅读体验

这是一个图上计数问题，数据范围很小，我们考虑进行状压 dp。

一个简单环原则上是不能经过重边的，因此我们要把二元环单独计数。

考虑大小 >2 的环怎么数。我们会发现，对于一个环，从任何一个点开始走一圈都是合法的。因此我们需要钦定一个环的起点是环上编号最大的点，使得一个环只会在一个点上产生贡献。

然而我们会发现至此还是错的。一个环从一个点出发可以顺时针走，也可以逆时针走。但是这样以来还是很好办，因为一个环会稳定地算成 2 个，最后输出时除以 2 就好了。

那么我们模仿旅行商问题设计状态。令 G_{i,j} 为图上 i,j 之间边的数量，设 f_{S,i} 表示从 S 中编号最大的节点出发（不妨称其为 st），走到 i 点的方案数量。那么最后统计答案时枚举环上的最后一个点 i，将 f_{S,i} \times G_{i,st} 计入答案。

至于如何转移，可以枚举下一个点 j，则 i \to j 的方案数为 G_{i,j}，因此有转移：

f_{S \cup \{j\},j} = f_{s \cup \{j\},j} + f_{S,i} \times G_{i,j}(j \not \isin S, i \isin S)

那么这道题就做完了，复杂度为 O(2^n n^2)。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define N 21
using namespace std;
const int MOD=998244353,inv2=MOD+1>>1;
int n,m,G[N][N],dp[1<<N][N],ans;
void add(int &x,int y){x+=y,x-=x>=MOD?MOD:0;}
main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1,u,v;i<=m;i++)
        scanf("%lld%lld",&u,&v),G[u][v]++,G[v][u]++;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)add(ans,G[i][j]*(G[i][j]-1)%MOD);
    for(int st=3;st<=n;st++)
    {
        memset(dp,0,sizeof(dp)),dp[1<<st-1][st]=1;
        for(int S=1<<st-1;S<(1<<st);S++)
            for(int i=1;i<=st;i++)if(S&(1<<i-1))
            {
                if(__builtin_popcountll(S)>2)add(ans,dp[S][i]*G[st][i]%MOD);
                for(int j=1;j<=st;j++)if(!(S&(1<<j-1)))
                    add(dp[S|(1<<j-1)][j],dp[S][i]*G[i][j]%MOD);
            }
    }
    ans=ans*inv2%MOD,printf("%lld\n",ans);
    return 0;
}