【2011 Greater New York Regional 】Problem H: Maximum in the Cycle of 1

也是一个数学题；

主要用到的是排列组合的知识，推推公式就行了，挺简单的；

唯一要注意的是A（0,0）=1；

在这个上面WA了几次，= =

代码：

 1 #include<stdio.h>
 2 #define ULL unsigned long long
 3 #define maxn 21
 4 using namespace std;
 5  
 6 ULL C[maxn+5][maxn+5];//范围可向上变更
 7 ULL A[maxn];
 8 void builtC(){
 9     memset(C,0,sizeof(C));
10     C[0][0]=1;
11     for(int i=1;i<=maxn;i++){
12         C[i][0]=C[i][i]=1;
13         for(int j=1;j<=i;j++){
14             C[i][j]=(C[i-1][j]+C[i-1][j-1]);
15         }
16     }
17     return ;
18 }
19 void builtA()
20 {
21    ULL a=1;
22    A[0]=1;
23    for(int i=1;i<=20;i++)
24    {
25        a=a*i;
26        A[i]=a;
27    }
28 }
29 int main()
30 {
31  builtC();
32  builtA();
33  int t;
34  while(~scanf("%d",&t))
35  {
36      int cas,n,k;
37      while(t--)
38      {
39          scanf("%d%d%d",&cas,&n,&k);
40          ULL ans=0;
41          if (k==1) {printf("%d %.0lf
",cas,(double)A[n-1]);continue;}
42          int sc1=n-k,sc2=k-1,sc3=k-2;
43          while(sc1<=n-2)
44          {
45              ans+=A[sc1]*A[sc2]*C[k-2][sc3];
46              sc1++;sc2--;sc3--;
47          }
48          printf("%d %.0lf
",cas,(double)ans);
49      }
50  }
51  return 0;
52 }

View Code