P2183 [國家集訓隊]禮物

題意：

有n個禮物，分給m個人，分給第i個人的禮物數量是wi，問送禮物的方案數。

題解：

擴展盧卡斯模板題
很容易看出和組合數有關的題目，對于總方案，完美可以將其分解為m個不同的方案數的乘積
比如樣例1：4個禮物，2個人，第一個人要1個禮物，則第一個人取走禮物的方案為$C_4^1$，第二個人要2個禮物，方案為$C_3^2$,總方案為$C_4^1?C_3^2=12$
現在改變順序：第二個人先拿禮物，$C_4^2$,然后第一個人拿禮物，$C_2^1$,總方案為$C_4^2?C_2^1=12$
完美可以發現，無論誰取走禮物，結果都是一樣的，那我們只需要按照所給禮物順序計算就行。
總方案為：$C_n^{w_1}?C_{n?w_1}^{w_2}?....\mathrm{m}\mathrm{o}\mathrm{d}p$
本題的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; }

總結

以上是生活随笔為你收集整理的P2183 [国家集训队]礼物（扩展卢卡斯）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。