Posted on 2009-04-24 10:00
杜仲当归 阅读(772)
评论(0) 编辑 收藏 引用
求N个点连通图的数量。
此题涉及到图论，组合数学，DP等诸多范畴，考虑起来颇为麻烦。
首先定下点1，点2.。将点2移除，此时点1和k - 1个点在同一连通块内，k>=1&&k<=n - 2 ，把它称作连通块P1。剩下的点2和n-k-1个点在同一连通块内，称为连通块P2，此时P2中的点必然和P1中的点不连通。这样就划分成两个子问题，分别求P1和P2的连通图数量。然后考虑P1P2在n-2个点中挑选k-1个点有几种选法。最后将P1P2相连。由于P2中除了点2外和P1均不连通，问题就转变为P1所有点向点2连线有几种连法？前提是至少有一条线从P1连向P2。把三个步骤相乘就得到答案。
#include <iostream>
#include <string>
using namespace std;
#define MAX 100
class BigNum
{
private:
int M; // mod
int numlen ( int n )
{
int ret = 0;
while ( n )
n /= 10, ret ++;
return ret ? ret : 1;
}
public:
int len;
long long l[MAX];
BigNum ()
{
M = 100000000;
memset ( l, 0, sizeof ( l ) );
len = 1;
}
~BigNum ()
{
}
BigNum operator = ( long long int x )
{
if ( x == 0 )
{
memset ( l, 0, sizeof ( l ) );
len = 1;
return *this;
}
len = 0;
while ( x )
{
l[len ++] = x % M;
x /= M;
}
return *this;
}
BigNum operator + ( const BigNum &b )
{
BigNum sum;
int maxlen = len > b.len ? len : b.len;
int i, c;
for ( i = 0, c = 0; i < maxlen; i ++ )
{
sum.l[i] = l[i] + b.l[i] + c;
if ( sum.l[i] >= M )
sum.l[i] -= M, c = 1;
else
c = 0;
}
if ( c )
sum.l[i] = 1, maxlen ++;
sum.len = maxlen;
return sum;
}
BigNum operator * ( const BigNum &b )
{
BigNum mul;
if ( l[0] == 0 && len == 1 || b.l[0] == 0 && b.len == 1 )
return mul;
int maxlen = len + b.len - 1;
int i, j, c;
for ( i = 0; i < len; i ++ )
for ( j = 0; j < b.len; j ++ )
{
long long t = mul.l[i + j] + l[i] * b.l[j];
mul.l[i + j] = t % M;
c = t / M;
if ( c )
mul.l[i + j + 1] += c;
}
if ( c )
maxlen ++;
mul.len = maxlen;
return mul;
}
void print ()
{
int i;
for ( i = len - 1; i >= 0; i -- )
{
if ( i == len - 1 )
printf ( "%d", l[i] );
else
{
int zerolen = 8 - numlen ( l[i] );
int j;
for ( j = 0; j < zerolen; j ++ )
printf ( "0" );
printf ( "%d", l[i] );
}
}
printf ( "\n" );
}
};
BigNum f[51];
long long int Binomial ( int n, int m )
{
int i;
if ( m > n / 2 )
m = n - m;
long long int ans = 1;
for ( i = 1; i <= m; i ++ )
ans = ans * ( n - i + 1 ) / i;
return ans;
}
void dp ()
{
f[1] = 1, f[2] = 1, f[3] = 4, f[4] = 38;
int i, k;
for ( i = 4; i <= 50; i ++ )
{
f[i] = 0;
for ( k = 1; k <= i - 1; k ++ )
{
BigNum temp, a, b;
a = Binomial ( i - 2, k - 1 ), b = ( 1ll << k ) - 1;
temp = f[k] * f[i - k] * a * b;
f[i] = f[i] + temp;
}
}
}
void test ()
{
printf ( "%lld\n", 1ll << 50 );
}
int main ()
{
//freopen ( "in.txt", "r", stdin );
//freopen ( "out.txt", "w", stdout );
//test ();
dp ();
int N;
while ( cin >> N && N )
f[N].print ();
return 0;
}