XDU 1149 卡尔的技能 II (容斥多重集组合阶乘逆元)

本文主要是介绍XDU 1149 卡尔的技能 II (容斥多重集组合阶乘逆元)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1149: 卡尔的技能 II

时间限制: 2 Sec 内存限制: 128 MB

题目链接：http://acm.xidian.edu.cn/problem.php?id=1149

题目分析：首先这是一个多重集组合问题，请见多重集组合，所有不超过k，那就是个典型的容斥问题了，先求出总的情况数C(n + m - 1, m)，然后用总的减去有至少1种元素超过k次加上至少有2种元素超过k次。。。有i种元素超过k次方案数是两部分的积
1. C(n, i)表示从n种里选出i种
2. C(n + m - i * (k + 1) - 1, m - i * (k + 1))，这是多重集组合公式，表示种类数为n，次数为m - i * (k + 1)的多重集组合，因为至少有i个超过k次，那么每个最少要分配k + 1，所以剩下的次数就是m - i * (k + 1)
求组合数的时候直接预处理阶乘和阶乘逆元，则可以在线O(1)求得，最后注意答案可能为负，因此要加个MOD

#include <cstdio>  
#define ll long long  
int const MOD = 1e9 + 7;  
int const MAX = 2e6 + 5;  
ll n, m, k;
ll fac[MAX + 5], inv_fac[MAX + 5];ll qpow(ll x, ll n)  
{  ll res = 1;  while(n)  {  if(n & 1)  res = (res * x) % MOD;  x = (x * x) % MOD;  n >>= 1;  }  return res;  
}  void Init_fac()
{fac[0] = 1;for(int i = 1; i <= MAX; i++)fac[i] = (fac[i - 1] * i) % MOD;inv_fac[MAX] = qpow(fac[MAX], MOD - 2);for(int i = MAX - 1; i >= 0; i--)inv_fac[i] = (inv_fac[i + 1] * (i + 1) % MOD) % MOD;
}ll C(ll n, ll i)
{if(i > n)return 0;return ((((fac[n] % MOD) * (inv_fac[i] % MOD)) % MOD) * (inv_fac[n - i] % MOD)) % MOD;
}int main()  
{   Init_fac();while(scanf("%lld %lld %lld", &n, &m, &k) != EOF){  if(n * k < m){printf("0\n");continue;}if(k > m)k = m;ll ans = C(n + m - 1, m), sign = -1;for(ll i = 1; i <= n; i++, sign = -sign)  {ll tmp = m - i * (k + 1);if(tmp < 0)break;ans = ((ans % MOD) + (sign * C(n, i) * C(n + tmp - 1, tmp)) % MOD) % MOD;}printf("%lld\n", (ans + MOD) % MOD);}  
}

这篇关于XDU 1149 卡尔的技能 II (容斥多重集组合阶乘逆元)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！