簡單環(huán)

題解:

題目求環(huán)的情況
如果我們直接枚舉會(huì)有很多重復(fù)，為了避免重復(fù)，我們枚舉起點(diǎn)，其他的點(diǎn)的序號都必須比起點(diǎn)大，也就是x->y，x一定小于y
dp[i][j]表示的是以i的第一個(gè)點(diǎn)作為起點(diǎn)的鏈的數(shù)量，j是終點(diǎn)
i是二進(jìn)制，表示選擇了哪些點(diǎn)
我們先當(dāng)作鏈來考慮
我們從點(diǎn)j到點(diǎn)t，

狀態(tài)轉(zhuǎn)移： dp[i|(1<<(t-1))][t]=(dp[i|(1<<(t-1))][t]+dp[i][j])%mo;

前置條件為：i的第t-1位為0，i的第j-1位上為1（也可以是dp[i][j]不為0），j到t有邊
現(xiàn)在我們就構(gòu)造了一個(gè)鏈，中間為t，鏈上的點(diǎn)為i中為1的部分，現(xiàn)在如何考慮環(huán)？我們將鏈?zhǔn)孜幌嘟蛹礊榄h(huán)，也就是我們找到i的二進(jìn)制下從低到高出現(xiàn)1的第一個(gè)位置z，然后與t相連，當(dāng)然z和t必須可連才行
統(tǒng)計(jì)答案時(shí)要除以2，因?yàn)槊總€(gè)環(huán)都統(tǒng)計(jì)了順時(shí)針和逆時(shí)針兩種情況
詳細(xì)看代碼

代碼:

#include<iostream> #include<stack> #include<set> #include<cstring> #include<cmath> #include<stdlib.h> #include<cstdio> #include<queue> #include<algorithm> #include<string> #include<vector> #include <queue> #include <bitset> #include <limits.h> using namespace std; typedef long long ll; const ll mo=998244353; int dp[(1<<20)+100][21]; int e[21][21]={0}; ll kk[50]; ll kpow(ll a,ll b) {ll ans=1;while(b){if(b&1) ans=(ans*a)%mo;a=(a*a)%mo;b>>=1LL;}return ans; } inline int ffs(int x) {for(int i=0;i<30;i++){if(x&(1<<i)) return i+1;}return 0; } inline int popcount(int x) { int num=0;for(int i=0;i<=20;i++){if(x&(1<<i)) num++;}return num; } int main() {ll inv2=kpow(2LL,mo-2);int n,m,k;scanf("%d%d%d",&n,&m,&k);int x,y;for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);e[x][y]=1;e[y][x]=1;}for(int j=1;j<=n;j++){dp[0|(1<<(j-1))][j]=1;}for(int i=1;i<=(1<<n)-1;i++){int x=ffs(i);//從低到高出現(xiàn)1的第一個(gè)位置 for(int j=1;j<=n;j++) if(dp[i][j]){for( int t=x+1;t<=n;t++){ if((i&(1<<(t-1)))||e[j][t]==0) continue;dp[i|(1<<(t-1))][t]=(dp[i|(1<<(t-1))][t]+dp[i][j])%mo;}int y=__builtin_popcount(i);//計(jì)算里面有多少個(gè)1 if(e[j][x]&&y>2) kk[y%k]=(kk[y%k]+dp[i][j])%mo;}}for(int i=0;i<k;i++)kk[i]=kk[i]*inv2%mo;for(int i=0;i<k;i++)printf("%lld\n",kk[i]);return 0; }

總結(jié)

以上是生活随笔為你收集整理的简单环题解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。