LightOJ 1102 Problem Makes Problem（组合数学）

Time Limit:2000MS     Memory Limit:32768KB     64bit IO Format:%lld & %llu

Description

As I am fond of making easier problems, I discovered a problem. Actually, the problem is 'how can you make n by adding k non-negative integers?' I think a small example will make things clear. Suppose n=4 and k=3. There are 15solutions. They are

1.      0 0 4

2.      0 1 3

3.      0 2 2

4.      0 3 1

5.      0 4 0

6.      1 0 3

7.      1 1 2

8.      1 2 1

9.      1 3 0

10.    2 0 2

11.    2 1 1

12.    2 2 0

13.    3 0 1

14.    3 1 0

15.    4 0 0

As I have already told you that I use to make problems easier, so, you don't have to find the actual result. You should report the result modulo 1000,000,007.

Input

Input starts with an integer T (≤ 25000), denoting the number of test cases.

Each case contains two integer n (0 ≤ n ≤ 106) and k (1 ≤ k ≤ 106).

Output

For each case, print the case number and the result modulo 1000000007.

Sample Input

4

4 3

3 5

1000 3

1000 5

Sample Output

Case 1: 15

Case 2: 35

Case 3: 501501

Case 4: 84793457

题意 ： 输入n,k，输出 将n分成k个非负整数之和的方案数。

思路： 这个想法很重要，以题目中的样例来说吧：

      n=4,k=3;

1.      0 0 4              ->       0       0        1         1         1         1

2.      0 1 3              ->       0       1        0         1         1         1

3.      0 2 2              ->       0       1        1         0         1         1

4.      0 3 1              ->       0       1        1         1         0         1

5.      0 4 0              ->       0       1        1         1         1         0

6.      1 0 3              ->       1       0        0         1         1         1

7.      1 1 2              ->       1       0        1         0         1         1

8.      1 2 1              ->       1       0        1         1         0         1

9.      1 3 0              ->       1       0        1         1         1         0

10.    2 0 2              ->       1       1        0         0         1         1

11.    2 1 1              ->       1       1        0         1         0         1

12.    2 2 0              ->       1       1        0         1         1         0

13.    3 0 1              ->       1       1        1         0         0         1

14.    3 1 0              ->       1       1        1         0         1         0

15.    4 0 0              ->       1       1        1         1         0         0

根据上述可知，原问题可转换成 ：在n+k-1个位置上插入k-1个0的方案总数 ；

所以 ans = C(n+k-1,k-1);

#include <iostream>
#include <cstdio>
#define LL long long
using namespace std;
const int maxn=2000005;
const int mod =1000000007;

LL f[maxn];
int n,k,T;

LL pow_mod(LL num,int t)    //  快速幂求逆元
{
    LL p=num,q=t,ret=1;
    while(q)
    {
        if(q & 1)  ret = ret*p%mod;
        q>>=1;
        p=p*p%mod;
    }
    return ret%mod;
}

void initial()
{
    f[0]=f[1]=1;
    for(int i=2;i<maxn;i++) f[i]=f[i-1]*i%mod;
}

int main()
{
     initial();
     scanf("%d",&T);
     for(int co=1;co<=T;co++)
     {
           scanf("%d %d",&n,&k);
           LL a=pow_mod(f[k-1],mod-2);
           LL b=pow_mod(f[n],mod-2);
           printf("Case %d: %lld\n",co,f[n+k-1]*a%mod*b%mod);
     }
     return 0;
}