Hdu 1521 排列组合

   a1 n1 
   a2 n2
   ...
   ak nk
n=n1+n2+...+nk
从n个数中选r个排列（不是组合噢）
// 指数型母函数
// 模板
#include <iostream>
#include <string>
#include<sstream>
#include <cmath>
#include <map>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define  LL __int64//long long
struct node
{
    LL u,d; // u/d
    node(){}
    node(LL a,LL b){
      u=a;
      d=b;
    }
    LL gcd(LL a,LL b)
    {
        LL r;
        while(r=a%b){a=b;b=r;}
        return b;
    }
    node operator +(node no)
    {
        LL da=gcd(d,no.d);
        LL son=no.d/da*u+d/da*no.u;
        LL mather=no.d/da*d;
        da=gcd(son,mather);
        return node(son/da,mather/da);
    }
}Ge[22],tp[22];
LL f[22];
int main()
{
  int i,j,k;
  f[1]=1;
  for(i=2;i<=10;i++)
    f[i]=f[i-1]*i;
  int n,m;

  while(scanf("%d %d",&n,&m)!=EOF)
  {
     // memset(Ge,0,sizeof(Ge));
      Ge[0].u=Ge[0].d=1;
      for(i=1;i<=m;i++)
      Ge[i].u=0,Ge[i].d=1;
       for(i=1;i<=m;i++)
           tp[i].u=0,tp[i].d=1;
      while(n--)
      {
         scanf("%d",&k);
        // memset(tp,0,sizeof(tp));

         for(i=1;i<=k&&i<=m;i++)
           for(j=0;j+i<=m;j++)
           {
             tp[i+j]=tp[i+j]+ node(Ge[j].u,Ge[j].d*f[i]);
             //printf("%I64d %I64d
",tp[i].u,tp[i].d);
           }
         for(i=1;i<=m;i++)
            Ge[i]=tp[i];//printf("%I64d %I64d
",Ge[i].u,Ge[i].d),
      }

      printf("%I64d
",f[m]/Ge[m].d*Ge[m].u);//f[m]*Ge[m].u);
  }
  return 0;
}