The Monkey King(hdu5201)

The Monkey King

Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 487 Accepted Submission(s): 166

Problem Description

As everyone known, The Monkey King is Son Goku. He and his offspring live in Mountain of Flowers and Fruits. One day, his sons get

Input

There are multiple test cases. In the first line of the input file there is an integer

Output

For each case，the output should occupies exactly one line.

See the sample for more details.

Sample Input

2

2 2

3 5

Sample Output

1

5
Hint





For the second case, there are five ways. They are
2 1 0 0 0
2 0 1 0 0
2 0 0 1 0
2 0 0 0 1
3 0 0 0 0

思路：隔板法+容斥+逆元;

先枚举第一个人分得的个数，然后我们考虑剩下的可以咋放，剩下的为n-i那么这些要给m-1个人，且可以为空，那么就是C(n-i+m-2,m-2)种，然后我们减去里面不符合情况的，我们枚举至少有k个不小于第一个人的个数的，那么我们就必须在这些人中给i个，然后剩下的在用分给m-1个人，F[j] = C(m-1,1)*C(n-(1+k)*j+m-2,m-2)

那么这些里面会有重复的，F[1] = C(1,1)f(1)+C(2,1)f(2)+C(3,1)f(3)+......;

F[2] = C(2,2)f(2) + C(3,2)f(3)+C(4,2)f(4)+....;

那么f（j）就是我们要的，那么我们可以知道F（1)-F(2) + F（3）-F(4)..... = f(1)+f(2)+...;

(1+x)^n+（1-x）^n = 2*(C(n,0)+C(n,2)+...)当x = 1的时候那么有偶数项等于2^(n-1) = 奇数项，那么C（n,1）-C(n,2)+C(n,3) ..+C(n,n) = 1;

所以要的到sum（f（j）） = F（1)-F(2) + F（3）-F(4)..... （奇加偶减）

复杂度（n*log(n)）

 1 #include <iostream>
 2 #include<algorithm>
 3 #include<string.h>
 4 #include<queue>
 5 #include<math.h>
 6 #include<set>
 7 #include<stdio.h>
 8 using namespace std;
 9 typedef long long LL;
10 LL N[200010];
11 LL NN[200010];
12 const LL mod = 1e9+7;
13 LL quick(LL n,LL m);
14 LL C(LL n,LL m);
15 int main(void)
16 {
17     int n;
18     scanf("%d",&n);
19     N[0] = 1;
20     int i,j;NN[0] = 1;
21     for(i = 1; i <= 200005; i++)
22     {
23         N[i] = N[i-1]*(LL)i%mod;
24         NN[i] = quick(N[i],mod-2);
25     }
26     //printf("%lld
",quick(6,mod-2));
27     while(n--)
28     {
29         int m,k;
30         scanf("%d %d",&m,&k);
31         LL sum = 0;
32         if(k == 1)
33             printf("%d
",k);
34         else
35         {
36             for(i = m; i >= 1; i--)
37             {
38                 LL x = m-i;
39                 LL y = k-1;
40                 LL an = C(x+y-1,y-1);
41                 for(j = 1; j <= k-1&&(LL)(j+1)*(LL)i<= m; j++)
42                 {
43                     x = k-1;
44                     y = j;
45                     LL akk = C(x,y);
46                     LL ab = m-(LL)(j+1)*(LL)i;
47                     ab = ab+k-2;
48                     LL bk = C(ab,k-2);
49                     if(j%2)
50                         an = an-bk*akk%mod;
51                     else an+=(bk*akk)%mod;
52                     an = an%mod;
53                 }
54                 sum = (sum+an)%mod;
55             }
56             printf("%lld
",(sum%mod+mod)%mod);
57         }
58     }
59 }
60 LL C(LL n,LL m)
61 {
62     LL ni = NN[n-m]*NN[m]%mod;
63     return ni*N[n]%mod;
64 }
65 LL quick(LL n,LL m)
66 {
67     LL ask = 1;
68     n%=mod;
69     while(m)
70     {
71         if(m&1)
72             ask = ask*n%mod;
73         n = n*n%mod;
74         m/=2;
75     }
76     return ask;
77 }