posts - 13, comments - 0, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

POJ 1737 高精度模板改进版

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, 
0sizeof ( l ) );
        len 
= 1;
    }

    
~BigNum ()
    
{
    }

    BigNum 
operator = ( long long int x )
    
{
        
if ( x == 0 )
        
{
            memset ( l, 
0sizeof ( 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;
}


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理