#191 sea（动态规划）

时间：2022-04-24 15:29:42

　　假设已经求出了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;

}

相关文章