正題

題目鏈接:https://www.ybtoj.com.cn/contest/68/problem/3

---

題目大意

求有多少個$n$個點$m$條邊的無向圖滿足

有連邊的點之間編號差不超過$k$

所有點的度數都為偶數

---

解題思路

因為$k$很小，所以我們考慮狀壓一個點前$k$個點的奇偶狀態。設$f_{i,j,s,0/1}$表示到第$i$個點連接了$j$條邊，前$k$個點奇偶狀態為$s$，然后點$i$的奇偶狀態。

然后轉移即可，每次加一個條邊即可，時間復雜度$O(2^{k}nm)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=32,XJQ=1e9+7; int n,m,k,pw[10],f[N][N][1<<9][2]; int main() {freopen("graph.in","r",stdin);freopen("graph.out","w",stdout);scanf("%d%d%d",&n,&m,&k);int MS=(1<<k);f[1][0][0][0]=1;for(int i=1;i<=n;i++){int lim=min(MS,(1<<i-1));for(int x=0;x<min(k,i-1);x++)for(int j=0;j<=m;j++)for(int s=0;s<lim;s++){int z=s^(1<<x);(f[i][j+1][z][1]+=f[i][j][s][0])%=XJQ;(f[i][j+1][z][0]+=f[i][j][s][1])%=XJQ;} // if(i==n)break;for(int j=0;j<=m;j++)for(int s=0;s<MS;s++){if(s&(1<<k-1))continue;int z=(s<<1)&(MS-1);(f[i+1][j][z][0]+=f[i][j][s][0])%=XJQ;(f[i+1][j][z|1][0]+=f[i][j][s][1])%=XJQ;}}printf("%d",f[n][m][0][0]); }

總結

以上是生活随笔為你收集整理的YbtOJ#20239-[冲刺NOIP2020模拟赛Day10]连边方案【状压dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。