【状压DP】简单环-蒲公英云

【状压DP】简单环

怎么办，感觉现在所谓会的算法都是云的

以为自己会，然后随便出一道题就不会

云玩家是吧

好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦

好焦虑好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑 好焦虑

c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m c n m

D-简单环_牛客竞赛动态规划专题班状压dp例题 (nowcoder.com)

题意：、

思路：

即使一万年前我就写过这种题了，这并不妨碍我现在还不会做

考虑状压DP

设dp[s][u]表示走过的点集是s，最后一个点是u的链的数量

注意，是链的数量！不是简单环的数量

统计出来链的数量，自然就能统计环的数量了

Code：

#include <bits/stdc++.h>
#define int long long
#define low(x) log2(x&(-x)) 
using namespace std;
const int mxn=22;
const int mxe=2e5+10;
const int mod=998244353;
int N,M,K,u,v;
int G[mxn][mxn],dp[(1<<20)][mxn];
int ans[mxn];
int ksm(int a,int b,int mod){
    int res=1;
    while(b){
        if(b&1) res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
}
void solve(){
    cin>>N>>M>>K;
    for(int i=1;i<=M;i++){
        cin>>u>>v;
        u--,v--;
        G[u][v]=G[v][u]=1;
    }
    for(int i=0;i<N;i++) dp[(1<<i)][i]=1;
    for(int s=1;s<(1<<N);s++){
        int st=low(s);
        for(int u=0;u<N;u++){
            if(((s>>u)&1)==0) continue;
            if(dp[s][u]==0) continue;
            for(int v=st+1;v<N;v++){
                if((s>>v)&1) continue;
                if(!G[u][v]) continue;
                dp[s|(1<<v)][v]=(dp[s|(1<<v)][v]+dp[s][u])%mod;
            }
            if(G[u][st]){
                int cnt=__builtin_popcount(s);
                if(cnt<3) continue;
                ans[cnt%K]=(ans[cnt%K]+dp[s][u])%mod;
            }
        }
    }
    for(int i=0;i<K;i++){
        cout<<ans[i]*ksm(2,mod-2,mod)%mod<<'\n';
    }
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int __=1;//cin>>__;
    while(__--)solve();return 0;
}