hdu 1521（指數型母函數）

//

n種物品中挑M個，看有多少種排列。

可能有重復的，意思就是同一種物品無論怎麼排列都只算做一種，所以當選某一件物品k次時就要 除以k!

2013-04-26

[cpp]
#include"stdio.h"  
#include"string.h"  
#include"math.h"  
int fact[12]; 
void fun() 
{ 
    int i; 
    fact[0]=1; 
    fact[1]=1; 
    for(i=2;i<=11;i++) 
        fact[i]=fact[i-1]*i; 
} 
int main() 
{ 
    int i,j,k; 
    int n,m; 
    int a[12]; 
    double c1[11],c2[11]; 
    fun(); 
    while(scanf("%d%d",&n,&m)!=-1) 
    { 
        memset(c1,0,sizeof(c1)); 
        memset(c2,0,sizeof(c2)); 
        for(i=0;i<n;i++) 
            scanf("%d",&a[i]); 
        for(i=0;i<=a[0];i++) 
            c1[i]=1.0/fact[i]; 
        for(i=1;i<n;i++) 
        { 
            for(j=0;j<=m;j++) 
            { 
                for(k=0;k<=a[i]&&j+k<=m;k++) 
                    c2[j+k]+=(c1[j]/fact[k]); 
            } 
            for(j=0;j<=m;j++) 
                c1[j]=c2[j],c2[j]=0; 
        } 
        double ans=c1[m]*1.0*fact[m]; 
        printf("%.0lf\n",ans); 
    } 
    return 0; 
}