师范大学 e: skyscrapers

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<cstring>
 4 #include<cstdlib>
 5 using namespace std;
 6 typedef __int64 LL;
 7 const LL mod = 1000000007;
 8 LL cnm[5002][5002];
 9 LL  dp[5002][5002];
10 
11 void prepare()
12 {
13     LL i,j;
14     for(i=0;i<=5000;i++)
15     {
16         cnm[0][i]=1;
17         cnm[i][0]=1;
18     }
19     for(i=1;i<=5000;i++)
20     {
21         for(j=1;j<=i&&j<=5000;j++)
22         {
23             if(i==j) { cnm[i][j]=1;continue;}
24             if(j==1) { cnm[i][j]=i;continue;}
25             cnm[i][j]=(cnm[i-1][j]+cnm[i-1][j-1])%mod;
26         }
27     }
28     dp[0][0]=1;
29     for(i=1;i<=5000;i++)
30         for(j=1;j<=5000;j++)
31             dp[i][j]=(dp[i-1][j-1]+((i-1)*dp[i-1][j])%mod)%mod;
32 }
33 int main()
34 {
35     LL n,a,b,cur;
36     LL l,r;
37     prepare();
38     while(scanf("%I64d%I64d%I64d",&n,&a,&b)>0)
39     {
40         if(n==0&&a==0&&b==0)break;
41         l=a;r=n-b+1;
42         for(cur=0;l<=r;l++)
43         {
44             cur=( cur+((cnm[n-1][l-1]*dp[l-1][a-1])%mod)*dp[n-l][b-1])%mod;
45         }
46         printf("%I64d
",cur);    
47     }
48     return 0;
49 }