XidianOJ 1149 卡尔的技能 II

本文主要是介绍XidianOJ 1149 卡尔的技能 II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

--正文

多重集合数 + 组合数取模

首先求出没有限制的选择方法C(n+m-1,m)

然后减掉至少有一个元素选择了k+1次的方法数，加上至少有两个元素选择了k+1次的方法数。。。以此类推

然后是组合数的计算

C(n,m) % p= (n! / (m! * (n-m)!)) % p

由乘法逆元的性质和费马小定理可以算出

C(n,m) % p= n! * (m!*(n-m)!)^(p-2)

后面的幂次使用快速幂可以轻松算出

#include <cstdio> 
#include <cstring> 
#include <algorithm> 
#include <cmath> 
#include <iostream> 
using namespace std;  
typedef long long LL;
#define MOD 1000000007
LL Fast_Mod(LL a,LL b){LL res = 1,base = a;while (b){if (b&1) res = (res*base) % MOD;base = (base*base) % MOD;b = b >> 1;}return res;
}
LL fac[2000009],invfac[2000009],n,m,k;
void Getfac(LL p){fac[0] = 1;int i;for (i=1;i<=p;i++){fac[i] = (fac[i-1]*i) % MOD;}invfac[p] = Fast_Mod(fac[p],MOD-2);for (i=p-1;i>=0;i--){invfac[i] = (invfac[i+1]*(i+1)) % MOD;}
}
LL Lucas(LL n,LL m){if (n < m) return 0;return ((fac[n] % MOD)*(invfac[m] % MOD) % MOD) * (invfac[n-m] % MOD) % MOD;
}
int main(){ Getfac(2000006);while(scanf("%lld %lld %lld",&n,&m,&k)!=EOF){ long long i;long long res = Lucas(n+m-1,m),sign = -1;for (i=1;i<=n;i++,sign = -sign){long long tmp = m - (k+1)*i; if (tmp < 0) break;res = (res % MOD + sign*Lucas(n,i)*Lucas(n+tmp-1,tmp)) % MOD;}printf("%lld\n",(res+MOD) % MOD);} return 0; 
}