hdu 1521(指数型母函数)

我会带着你远行 2022-06-10 07:41 162阅读 0赞

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div> 
     <span style="margin-right:20px;"></span> 
    </div></td> 
  </tr> 
  <tr> 
   <td align="center"><h1 style="color:#1A5CC8;">排列组合</h1><strong><span style="font-family:Arial;font-size:12px;color:#008000;"><strong>Time Limit: 2000/1000 MS (Java/Others)&nbsp;&nbsp;&nbsp;&nbsp;Memory Limit: 65536/32768 K (Java/Others)<br>Total Submission(s): 4354&nbsp;&nbsp;&nbsp;&nbsp;Accepted Submission(s): 1857<br></strong></span></strong><br><br> 
    <div>
      Problem Description 
    </div> 
    <div>
      有n种物品，并且知道每种物品的数量。要求从中选出m件物品的排列数。例如有两种物品A,B，并且数量都是1，从中选2件物品，则排列有"AB","BA"两种。 
     <br> 
    </div> 
    <div>
      &nbsp; 
    </div><br> 
    <div>
      Input 
    </div> 
    <div>
      每组输入数据有两行，第一行是二个数n,m(1&lt;=m,n&lt;=10)，表示物品数，第二行有n个数，分别表示这n件物品的数量。 
    </div> 
    <div>
      &nbsp; 
    </div><br> 
    <div>
      Output 
    </div> 
    <div>
      对应每组数据输出排列数。(任何运算不会超出2^31的范围) 
    </div> 
    <div>
      &nbsp; 
    </div><br> 
    <div>
      Sample Input 
    </div> 
    <div>
      2&nbsp; 2 
    </div> 
    <div>
      1&nbsp; 1 
    </div> 
    <div>
      &nbsp; 
    </div><br> 
    <div>
      Sample Output 
    </div> 
    <div>
      2 
    </div> 
    <div> 
     <br> 
    </div> 
    <div>
      题目分析:这是另一种母函数类型（指数型母函数） （模板题目) 
    </div> 
    <div> 
     <img src="https://img-blog.csdn.net/20170813203820776?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvd3VzdF9jeWw=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt=""> 
    </div> 
    <div> 
     <pre><code>#include&lt;iostream&gt;
#include&lt;cstdio&gt;
#include&lt;cmath&gt;
#include&lt;cstring&gt;
using namespace std;

int a[100];
double c1[100],c2[100];
double factorial(int n)
{
    double ans=1.0;
    for (int i=1;i&lt;=n;i++)
        ans*=i;
    return ans;
}
int main()
{
    int n,m;
    while (scanf("%d%d",&amp;n,&amp;m)!=EOF) {
        memset (c1,0,sizeof (c1));
        memset (c2,0,sizeof (c2));
        for (int i=0;i&lt;n;i++)
            scanf("%d",&amp;a[i]);
        for (int i=0;i&lt;=a[0];i++)
            c1[i]=1.0/factorial(i);
        for (int i=1;i&lt;n;i++) {
            for (int j=0;j&lt;=m;j++) {
                for (int k=0;k+j&lt;=m&amp;&amp;k&lt;=a[i];k++)
                    c2[j+k]+=c1[j]/factorial(k);//只需要注意这里就行了，前面的系数不再是1了，而是1/k!
            }
            for (int k=0;k&lt;=m;k++) {
                c1[k]=c2[k];
                c2[k]=0;
            }
        }
        printf("%.0lf\n",c1[m]*factorial(m));

}
    return 0;
}
</code></pre> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div></td> 
  </tr> 
 </tbody> 
</table>