【状压DP】简单环

柔情只为你懂 2024-03-17 08:57 57阅读 0赞

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

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

**云玩家是吧**

**好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦 好烦**

**好焦虑 好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑** **好焦虑**

**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)][D-_dp_ _nowcoder.com]

题意：、![ff65f75b3ce445c7a28bdc21ce69cd6f.png][]

思路：

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

考虑状压DP

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

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

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

![60af52c60fe041c485963984a2f662e5.png][]

![7312412c15204668ad91e2f1d930fb0f.png][]

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;
    }

[D-_dp_ _nowcoder.com]: https://ac.nowcoder.com/acm/contest/28259/D
[ff65f75b3ce445c7a28bdc21ce69cd6f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/820b7621186f41a7aa3756d8294eb10c.png
[60af52c60fe041c485963984a2f662e5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/0b961836211a4d33b996ba1c3ac2b916.png
[7312412c15204668ad91e2f1d930fb0f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/265c93d9203a4a318e5eea13965949d4.png