假設已經求出了i個點j個橋的連通圖數量f[i][j]，容易由此推出最終答案，套路地枚舉1號點所在連通塊大小即可。

　　假設已經求出了i個點的邊雙連通圖數量h[i]，考慮由此推出f[i][j]。可以枚舉其中一座橋將圖劃分成兩個部分，固定1號點在其中一端，將橋兩端的部分方案數相乘即可。這樣每種方案被考慮的次數就是其中橋的個數，最后再除一下橋個數即可。

　　考慮求h[i]。事實上直接將連通圖數量減去f[i][1~i-1]即可。連通圖計數就是經典題了，套路差不多。

#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #define ll long long #define P 1000000007 #define N 55 char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() {int x=0,f=1;char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f; } int n,m,f[N][N],g[N][N],h[N],C[N][N],inv[N],p[N*N],ans; void inc(int &x,int y){x+=y;if (x>=P) x-=P;} int main() {freopen("sea.in","r",stdin);freopen("sea.out","w",stdout);n=read(),m=read();C[0][0]=1;for (int i=1;i<=n;i++){C[i][0]=C[i][i]=1;for (int j=1;j<i;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;}inv[0]=inv[1]=1;for (int i=2;i<=n;i++) inv[i]=P-1ll*inv[P%i]*(P/i)%P;p[0]=1;for (int i=1;i<=n*n;i++) p[i]=(p[i-1]<<1)%P;h[1]=1;for (int i=2;i<=n;i++){for (int j=1;j<i;j++)inc(h[i],1ll*h[j]*C[i-1][j-1]%P*p[C[i-j][2]]%P);h[i]=(p[C[i][2]]-h[i]+P)%P;}f[1][0]=1;g[1][0]=1;for (int i=2;i<=n;i++){for (int j=1;j<i;j++){for (int x=1;x<i;x++)for (int y=0;y<j;y++)inc(f[i][j],1ll*f[x][y]*f[i-x][j-y-1]%P*x%P*(i-x)%P*C[i-1][x-1]%P);g[i][j]=f[i][j]=1ll*f[i][j]*inv[j]%P;for (int x=1;x<i;x++)for (int y=0;y<=j;y++)inc(g[i][j],1ll*g[i-x][j-y]*f[x][y]%P*C[i-1][x-1]%P);}f[i][0]=h[i];for (int j=1;j<i;j++) inc(f[i][0],P-f[i][j]);g[i][0]=p[C[i][2]];for (int j=1;j<i;j++) inc(g[i][0],P-g[i][j]);}int ans=0;for (int i=0;i<=m;i++) inc(ans,g[n][i]);cout<<ans;return 0; }

轉載于:https://www.cnblogs.com/Gloid/p/10371858.html

總結

以上是生活随笔為你收集整理的#191 sea（动态规划）的全部內容，希望文章能夠幫你解決所遇到的問題。

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