本文主要是介绍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
题目链接: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 (容斥 多重集组合 阶乘逆元)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!