当前位置:编程学习 > C/C++ >>

hdu1521-排列组合

指数型母函数
 
G(x) = ( 1 + x / 1!  + (x^2)/(2!) + .....+ (x ^ n1 ) / (n1!)  ) * (( 1 + x / 1!  + (x^2)/(2!) + .....+ (x ^ n2 ) / (n2!)*.............*(( 1 + x / 1!  + (x^2)/(2!) + .....+ (x ^ nk) / (nk!)  )  
 
求x^m的系数转换成temp / ( m ! )  ;
 
然后求解时,temp * (m! ) 就是x ^ m的系数
 
#include<map>  
#include<set>  
#include<list>  
#include<cmath>  
#include<ctime>  
#include<deque>  
#include<stack>  
#include<bitset>  
#include<cstdio>  
#include<vector>  
#include<cstdlib>  
#include<cstring>  
#include<iomanip>  
#include<numeric>  
#include<sstream>  
#include<utility>  
#include<iostream>  
#include<algorithm>  
#include<functional>  
  
using namespace std ;  
  
double fac[ ] = { 1 , 1 , 2 , 6 , 24 , 120 , 720 , 5040 , 40320 , 362880 , 3628800 , 39916800 } ;  
  
int main()  
{  
    int n , m ;  
    double a[ 11 ] , b[ 11 ] , num1[ 11 ], num2[ 11 ];  
    while( scanf( "%d%d" , &n , &m ) != EOF )  
    {  
        for( int i = 0 ; i < n ; ++i )  
        {  
            scanf( "%lf" , &a[ i ] ) ;  
        }  
        for( int i = 0 ; i <= m ; ++i )  
            num1[ i ] = num2[ i ] = 0.0 ;  
        for( int i = 0 ; i <= a[ 0 ] ; ++i )  
        {  
            num1[ i ] = 1.0 / fac[ i ] ;  
        }  
        for( int i = 1 ; i < n ; ++i )  
        {  
            for( int j = 0 ; j <= m ; ++j )  
            {  
                for( int k = 0 ; k <= a[ i ] && k + j <= m ; ++k )  
                {  
                    num2[ k + j ] += ( num1[ j ] / fac[ k ] ) ;  
                }  
            }  
            for( int j = 0 ; j <= m ; ++j )  
            {  
                num1[ j ] = num2[ j ] ;  
                num2[ j ] = 0 ;   
            }  
        }  
        printf( "%.lf\n" , num1[ m ] * fac[ m ] ) ;  
    }  
    return 0;  
}  

 


补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,