外贸seo网站推广公司,查建设工程规划许可证在哪个网站,枣庄网站设计,网站建设的目标客户分析P2183 [国家集训队]礼物
题意#xff1a;
有n个礼物#xff0c;分给m个人#xff0c;分给第i个人的礼物数量是wi#xff0c;问送礼物的方案数。
题解#xff1a;
扩展卢卡斯模板题 很容易看出和组合数有关的题目#xff0c;对于总方案#xff0c;完美可以将其分解为…P2183 [国家集训队]礼物
题意
有n个礼物分给m个人分给第i个人的礼物数量是wi问送礼物的方案数。
题解
扩展卢卡斯模板题 很容易看出和组合数有关的题目对于总方案完美可以将其分解为m个不同的方案数的乘积 比如样例14个礼物2个人第一个人要1个礼物则第一个人取走礼物的方案为C41C_{4}^{1}C41第二个人要2个礼物方案为C32C_{3}^{2}C32,总方案为C41∗C3212C_{4}^{1}*C_{3}^{2}12C41∗C3212 现在改变顺序第二个人先拿礼物C42C_{4}^{2}C42,然后第一个人拿礼物C21C_{2}^{1}C21,总方案为C42∗C2112C_{4}^{2}*C_{2}^{1}12C42∗C2112 完美可以发现无论谁取走礼物结果都是一样的那我们只需要按照所给礼物顺序计算就行。 总方案为Cnw1∗Cn−w1w2∗....modpC_{n}^{w_{1}}*C_{n-w_{1}}^{w_{2}}*....\bmod pCnw1∗Cn−w1w2∗....modp 本题的p不一定是质数此时就没办法求组合数就要用的扩展卢卡斯定理该算法就是专门解决模数p不是质数的情况
代码
#include bits/stdc.h
#include cstdio
using namespace std;
#define FOR(i, a, b) for (ll i a; i b; i)
#define DEC(i, a, b) for (ll i a; i b; --i)typedef long long ll;ll mod;void exgcd(ll a, ll b, ll x, ll y)
{if (!b) {x 1, y 0;return;}exgcd(b, a % b, y, x);y- a / b * x;return;
}inline ll inv(ll n, ll p)
{ll x, y;exgcd(n, p, x, y);return (x p) % p;
}ll qpow(ll base, ll p, ll mod)
{ll ret 1;for (; p; p 1, base base * base % mod)if (p 1)ret ret * base % mod;return ret;
}ll CRT(int n, ll* a, ll* m)
{ll M 1, ret 0;FOR(i, 1, n) M* m[i];FOR(i, 1, n){ll w M / m[i];ret (ret a[i] * w % mod * inv(w, m[i]) % mod) % mod;}return (ret mod) % mod;
}ll calc(ll n, ll q, ll qk)
{if (!n)return 1;ll ret 1;FOR(i, 1, qk)if (i % q)ret ret * i % qk;ret qpow(ret, n / qk, qk);FOR(i, n / qk * qk 1, n)if (i % q)ret ret * (i % qk) % qk;return ret * calc(n / q, q, qk) % qk;
}ll multiLucas(ll n, ll m, ll q, ll qk)
{int cnt 0;for (ll i n; i; i/ q)cnt i / q;for (ll i m; i; i/ q)cnt- i / q;for (ll i n - m; i; i/ q)cnt- i / q;return qpow(q, cnt, qk) * calc(n, q, qk) % qk * inv(calc(m, q, qk), qk) % qk * inv(calc(n - m, q, qk), qk) % qk;
}ll exLucas(ll n, ll m, ll p)
{int cnt 0;ll qk[20], a[20]; //存放所有的 q^k 和待合并答案的结果for (ll i 2; i * i p; i) //质因数分解{if (p % i 0) {qk[cnt] 1;while (p % i 0)qk[cnt]* i, p/ i;a[cnt] multiLucas(n, m, i, qk[cnt]);}}if (p 1)qk[cnt] p, a[cnt] multiLucas(n, m, p, p);return CRT(cnt, a, qk); //CRT 合并答案
}
int w[20];
int main()
{ll n, m, p;scanf(%lld %lld %lld, p, n, m);mod p;int sum 0;for (int i 1; i m; i)cin w[i], sum w[i];if (sum n) {printf(Impossible);return 0;}ll ans 1;for (int i 1; i m; i) {ans ans * exLucas(n, w[i], mod) % mod;n- w[i];}printf(%lld\n, ans);return 0;
}
