Light OJ 1102

题意： 给你一个数 N ， 求分成 K 个数 （可以为 0 ） 的种数；

思路： 类似 在K个抽屉放入 N 个苹果， 不为0， 就是 在 n-1 个空隙中选 m-1个；

　　　 为 0， 就可以先在 K 个抽屉一个苹果， 之后类似了；

　　　 故答案就是 C（N+K-1， K-1）；

　　　 数据大， 还控制内存。。。 按位乘 + 逆元

#include<bits/stdc++.h>

using namespace std;

typedef int LL;

const int maxn = 2000000 + 131;

const LL MOD = 1000000007;

LL Mul(LL a, LL b, LL m)

{

    a = (a % m + m) % m;

    b = (b % m + m) % m;

    LL ret = 0;

    while(b)

    {

        if(b & 1) ret = (ret + a) % m;

        b >>= 1;

        a <<= 1;

        a %= m;

    }

    return ret;

}

LL Pow_Mod(LL a, LL n, LL m)

{

    LL ret = 1;

    while(n)

    {

        if(n & 1) ret = Mul(ret, a, m);

        n >>= 1;

        a = Mul(a, a, m);

    }

    return ret;

}

LL Num[maxn], Inv[maxn];

void Init()

{

    Num[0] = 1;

    for(LL i = 1; i < maxn; ++i) Num[i] = Mul(Num[i-1], i, MOD);

    Inv[maxn-1] = Pow_Mod(Num[maxn-1], MOD-2, MOD);

    for(LL i = maxn-2; i >= 0; --i) Inv[i] = Mul(Inv[i+1], (i+1), MOD);

}

LL C(LL m, LL n, LL mod)

{

    if(n == 0 || n == m) return 1;

    LL ret = 1;

    LL s = m - n;

    ret = Mul(Num[m], Inv[s], mod);

    ret = Mul(ret, Inv[n], mod);

    return ret;

}

int main()

{

    Init();

    int t;

    LL n, k;

    scanf("%d",&t);

    for(int kase = 1; kase <= t; ++kase)

    {

        scanf("%d %d",&n, &k);

        printf("Case %d: %d\n",kase, C(n+k-1, k-1, MOD));

    }

}