LightOJ

链接：

题意：

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 15 solutions. They are

```
 0 0 4
```
```
 0 1 3
```
```
 0 2 2
```
```
 0 3 1
```
```
 0 4 0
```
```
 1 0 3
```
```
 1 1 2
```
```
 1 2 1
```
```
 1 3 0
```
2 0 2
2 1 1
2 2 0
3 0 1
3 1 0
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.

思路：

转化为将n个物体分成k快，要插k-1个板，但是因为可以分出0个物体，所以我们加上k，保证每个部分必须有一个，答案就是C(n+k-1, k-1)
使用卢卡斯定理和逆元

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MOD = 1e9+7;
const int MAXN = 1e6+10;

int Fac[MAXN*2];
int n, k;

void GetFac()
{
    Fac[0] = Fac[1] = 1;
    for (int i = 2;i < MAXN*2+10;i++)
        Fac[i] = (1LL*Fac[i-1]*i)%MOD;
}

LL PowMod(LL a, LL b, LL p)
{
    LL res = 1;
    while(b)
    {
        if (b&1)
            res = res*a%p;
        a = a*a%p;
        b >>= 1;
    }
    return res;
}

LL C(LL n, LL m, LL p)
{
    if (n == m)
        return 1;
    if (n < m)
        return 0;
    return (1LL*Fac[n]*PowMod(1LL*Fac[m]*Fac[n-m]%p, p-2, p))%p;
}

LL Lucas(LL n, LL m, LL p)
{
    if (m == 0)
        return 1;
    return (C(n%p, m%p, p)*Lucas(n/p, m/p, p))%p;
}

int main()
{
    // freopen("test.in", "r", stdin);
    GetFac();
    int t, cnt = 0;
    scanf("%d", &t);
    while (t--)
    {
        printf("Case %d:", ++cnt);
        scanf("%d%d", &n, &k);
        printf(" %lld
", Lucas(n+k-1, k-1, MOD));
    }
    

    return 0;
}