题意: 给你一个数 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));
}
}
05-11 14:40