#191 sea（动态规划）

　　假设已经求出了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（动态规划）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。