正題

題目鏈接:https://atcoder.jp/contests/arc115/tasks/arc115_d

---

題目大意

給出$n$個點$m$條邊的一張無向圖，對于每個$k\in [1,n]$ 求恰好有$k$個奇數入度點的生成子圖數量。

$1\le n,m\le 5000$

---

解題思路

考慮有$k$個奇入度點的圖有什么性質，既然是入度的奇偶性可以從歐拉回路入手。新建一個點，向一張有$k$個入度為奇數的點的圖上的$k$個點連邊，那么有且僅有一個方案使得圖存在歐拉回路。

所以我們可以先隨便向圖上的$k$個點連邊，然后再找圖上存在歐拉回路的圖的數量。至于怎么尋找存在歐拉回路的圖的數量，首先我們搞出一棵圖的生成樹，顯然樹上不存在歐拉回路，而所有的環（也就是存在歐拉回路的圖）都可以由每條樹邊構成的環選出若干個將重復的部分取反得到。

所以$n$個點$m$條邊的連通圖的歐拉回路數量就是$2^{m?n+1}$，如果而我們提前連接了$k$條邊的點必須選擇，所以這些邊不會增加歐拉回路的數量，所以答案就是$\left(\genfrac{}{}{0ex}{}{n}{k}\right)\times 2^{m?n+1}$。

然后會發現還是有點問題，因為圖沒有保障連通，那么設$f_i$表示目前連接了$i$條新邊的方案，然后每個連通塊暴力轉移就好了。

時間復雜度：$O(n^2)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=5100,P=998244353; struct node{ll to,next; }a[N<<1]; ll n,m,sun,sum,tot,ls[N],C[N][N],pw[N<<1],f[N]; bool v[N]; void addl(ll x,ll y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } void dfs(ll x){v[x]=1;sun++;for(ll i=ls[x];i;i=a[i].next){sum++;if(!v[a[i].to])dfs(a[i].to);}return; } signed main() {scanf("%lld%lld",&n,&m);for(ll i=1,x,y;i<=m;i++){scanf("%lld%lld",&x,&y);addl(x,y);addl(y,x);}C[0][0]=pw[0]=1;for(ll i=1;i<N*2;i++)pw[i]=pw[i-1]*2ll%P;for(ll i=1;i<=n;i++)for(ll j=0;j<=i;j++)C[i][j]=(C[i-1][j]+(j?C[i-1][j-1]:0))%P;f[0]=1;for(ll i=1;i<=n;i++)if(!v[i]){sum=sun=0;dfs(i);sum/=2;for(ll j=n;j>=0;j--){if(j&1)continue;f[j]=f[j]*pw[sum-sun+1]%P;for(ll k=2;k<=min(sun,j);k+=2)(f[j]+=f[j-k]*pw[sum-sun+1]%P*C[sun][k]%P)%=P;}}for(ll i=0;i<=n;i++)printf("%lld\n",f[i]);return 0; }

總結

以上是生活随笔為你收集整理的ARC115D-Odd Degree【dp,欧拉回路】的全部內容，希望文章能夠幫你解決所遇到的問題。

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