hdu 1521配列組合せ指数型母関数
指数関数の式(いずれか):
指数次一般解の問題:n色の球が既知で,1種X 1個目,2種X 2個目,3種X 3個目..そこからm個のシナリオ数(組合せ数)を求める.
公式のak/k!求めた組合せ数であり,akは配列数である.
係数を求めるときはそれぞれiの階乗で割るだけでよい
指数型は階乗を使うので、総球数が100より大きい場合は他の方法があればできるだけ使わないでください(私だけ)
配列の組合せ
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 1084 Accepted Submission(s): 449
Problem Description
n種類の品物があり、それぞれの品物の数を知っています.その中からm品を選ぶ配列数を要求する.例えば、2つのアイテムA、Bがあり、いずれも数が1で、その中から2つのアイテムを選ぶと、「AB」、「BA」の2種類が並んでいます.
Input
各入力データは2行あり、1行目は2個の数n,m(1<=m,n<=10)であり、物品数を表し、2行目はn個の数であり、それぞれこのn個の物品の数を表す.
Output
データのセットごとに配列数を出力します.(いずれの演算も2^31の範囲を超えない)
Sample Input
Sample Output
#include #include double c1[1000],c2[1000]; int num[100]; double jc(int x) { int i; double sum=1.0; for(i=1;i<=x;i++) sum=sum*i; return sum; } int main(){int i,j,k,n,m;while(scanf("%d%d",&n,&m)!=EOF){for(i=1;i<=n;i++)scanf("%d",&num[i]);memset(c 1,0,sizeof(c 1));memset(c 2,0,sizeof(c 2));for(i=0;i<=num[1];i+)/注意各物品は重量が1の分銅c 1[i]=1.0/1.0//m[i]=1.0/m[i];f(c 2))));for(i=0;for(i=0;i<=0;i<=num[1];i jc(i);for(i=2;i<=n;i+){for(j=0;j<=m;j++){for(k=0;k+j<=m&&k<=num[i]*1;k+)/val[i]はいずれも1なので直接k++c 2[j+k]+=c 1[j]/jc(k); } for(k=0;k<=m;k++) {
c1[k]=c2[k]; c2[k]=0; } } printf("%.0lf",c1[m]*jc(m));//に乗る
} }
指数次一般解の問題:n色の球が既知で,1種X 1個目,2種X 2個目,3種X 3個目..そこからm個のシナリオ数(組合せ数)を求める.
公式のak/k!求めた組合せ数であり,akは配列数である.
係数を求めるときはそれぞれiの階乗で割るだけでよい
指数型は階乗を使うので、総球数が100より大きい場合は他の方法があればできるだけ使わないでください(私だけ)
配列の組合せ
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 1084 Accepted Submission(s): 449
Problem Description
n種類の品物があり、それぞれの品物の数を知っています.その中からm品を選ぶ配列数を要求する.例えば、2つのアイテムA、Bがあり、いずれも数が1で、その中から2つのアイテムを選ぶと、「AB」、「BA」の2種類が並んでいます.
Input
各入力データは2行あり、1行目は2個の数n,m(1<=m,n<=10)であり、物品数を表し、2行目はn個の数であり、それぞれこのn個の物品の数を表す.
Output
データのセットごとに配列数を出力します.(いずれの演算も2^31の範囲を超えない)
Sample Input
2 2
1 1
Sample Output
2
#include
c1[k]=c2[k]; c2[k]=0; } } printf("%.0lf",c1[m]*jc(m));//に乗る
} }