题解 P2183 【[国家集训队]礼物】
___new2zy___
2018-08-15 16:25:31
# 题解 P2183 [国家集训队]礼物
题目传送门:
https://www.luogu.org/problemnew/show/P2183
==========================================
不得不说这是我做过的最正经的一道黑题了= =
在这里先吐槽一下：~~**数论真恶心**~~
很是佩服这题的第一个题解，就是有点小蒙，我来给大家讲一下我自己的理解方式
希望同学们能理解本题的核心**数论算法**：
**扩展卢卡斯定理**(ExLucas)
（这题其实可以当个模板题来做= =）
**前置知识**:
扩展欧几里得(Exgcd),乘法逆元,
中国剩余定理(CRT),Lucas定理(不必备)
（其实理解了做法也没什么难的对吧）（快逃）
==========================================
**简化版题面**:
你手中一共有**n件礼品**，你有**m个好~~(基)~~友**，
你打算**送给每个人wi件礼品**，
请你求出送出礼品的**方案数**，并让**答案对p取模**
请注意，**礼物**之间**两两不同**
==========================================
~~可能本人废话比较多，欢迎来吐槽~~
看完题目emmm。。。让我冷静一下= =
我们不妨假设**所有朋友收到的礼物数之和sum**:
sum=∑(i:1~m)wi
如果记**答案为ans**的话,那么有:
ans={C(n,sum)*C(sum,w1)*C(sum-w1,w2)*...*C(wi,wi)}%p
在上式中，C(n,m)代表组合数，每一项组合数乘在一起就是ans
那么**如果n<sum显然无解**，**即"impossible"**
（礼物不够当然没法送出去啦QAQ）
emmm....继续冷静思考，发现好像很简单？(逃
~~（只要**暴力递推计算**就好啦）~~
但是，如果我们**直接递推暴力求解ans**的话，那么会发现**时间复杂度不能接受**：
题目中给定的n的范围是1e9，预处理时直接递推求阶乘的话估计就要跑个很长时间吧= =所以这种做法显然是不可取的
那么这样就很难受，继续思考= =
"n很大，还要求组合数取模，那么用**Lucas定理吧**"
灵机一动，想到在数论问题中，对于类似于
C(n,m)%p(**必须保证p为prime**)的问题，
我们有一个定理:**Lucas定理**
这个定理大概长这个样子:
**Lucas(n,m)=C(n%p,m%p)*Lucas(n/p,m/p)**
其中Lucas(n,m)其实就是要计算的式子C(n,m)%p
对于这个定理，在此就不证明了~~(我比较菜所以不会证明)~~
**(注意:Lucas定理适用于n<=1e5)**
回到这题上来。。。
读者会发现，，好像我之前说的是废话= =
这个题n<=1e9好吧！！你在逗我？没法做。。
先淡定一下，到了这里其实已经离正解不远了，毕竟求解有了一定的方向
再次陷入沉思= =发现我们的**Lucas定理不可以直接使用**，因为题目中还有一个很致命的**限制条件**:
p<=1e9（此外什么也没说）
那么就抛来一个很重要的问题:**模数p不保证是质数**
那么导致我们如果**直接用逆元取模**的话不行，因为可能在这些阶乘中出现取模，这样答案直接就变为0了，因此我们要尝试把这些数提取出来。
emmm。。。恐怖如斯= =根本没法做了啊
但是我们发现,题目中给了提示:
设P=p1^c1*p2^c2*p3^c3*…*pt^ct,pi为质数。
其实这是数论中的**唯一分解定理**：
任意大于1的正整数N,存在唯一分解式N=p1^c1*p2^c2*...*pi^ci
其中p1~pi是质数,^是次方,c1~ci是次数
那么又可以很自然的想到:
我们可以将分子分母都对于p的唯一分解式中的每一项(即pi^ci)取模(就保证是prime了)，最后将每一项用CRT合并就得到了解
我们不妨再来考虑一下**组合数取模的计算公式**:
**C(n,m)%p={fac(n)/[fac(m)*fac(n-m)]}%p**
(注意，这里只是形式，实际上除法不能直接取模)
其中fac(x)表示x的阶乘，即x!
如果拆分的话，我们可以对于n!,m!,(n-m)!分别%p再进行合并即可求出答案
又可以注意到，其实整个问题就剩下了一个式子：
求解(x!)%(pi^ci),保证pi为质数
对于这个式子展开可以发现，它的**求解分为三部分**:
1. 在x!中,若存在pi的倍数那么就可以拆出来,与pi^ci抵消，即可以转化为**子问题**：求**(x/pi)!%pi^ci**，只需要**递归**下去**求解**就行了
2. n!中可能有会包含多个完整的1~pi^ci-1（在%pi^ci下的剩余系），这部分可以先预处理一下(pi^ci-1)! (注意是不包含pi的倍数的阶乘，因为我们还要记录一下阶乘中pi的次数最后一起处理)，然后pi的若干次幂用快速幂处理。
3. 那么进行完1,2两步之后，对于剩下的部分直接求一发逆元计算组合数，最后合并即可（扩欧求逆元，中国剩余定理合并）
有些懵逼？我来举个栗子食用更佳哈：
假设pi=5，展开阶乘可以发现：
n!= (1*2*3*4*6*7*8*9*11*…)*5^(n/5)*(n/5)!
(乘号*没了555，变成了斜体请自行脑补)
那么我们直接提取出所有pi=5的倍数，正好分为三部分，直接按步骤上面计算就行了
其实以上就是~~(最恶心的)~~**数论算法:扩展卢卡斯定理(ExLucas)**
讲到这里。。。突然发现这东西好像和卢卡斯定理一点关系没有= =（所以Lucas不是必备的知识）
大概思路讲完了，我们在放代码之前可以来总结一下这次的求解方法，即**扩展卢卡斯定理(ExLucas)**
**扩展卢卡斯定理适用于计算任意的C(n,m)%p问题，其中n,m,p为任意正整数**
求解过程主要应用了**乘法逆元**（**扩欧Exgcd**求）、**中国剩余定理**(CRT也就只有一行)、带取模**快速幂**（码量很小）
总体来说思路还是很清楚的吧
那么好啦，既然有了解决方案，题目里的式子就很好求了吧，放个代码code~~~
PS:代码里也有解释哦
```cpp
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
typedef long long ll;
const int inf=1e9+7;
inline ll poww(ll a,ll b,ll mod)//快速幂
{
ll base=a,ans=1;
while(b)
{
if(b&1)
ans=(1ll*ans*base)%mod;
base=(1ll*base*base)%mod;
b>>=1;
}
return 1ll*ans;
}
inline ll read()//快读
{
ll p=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}
return 1ll*f*p;}
ll n,m,sum,mod,ans=1,A[19];
inline 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;
}
inline ll rev(ll k,ll p)
//求k在mod p下的逆元(转换一下变成正整数)
{
if(!k)return 0;
ll x=0,y=0,a=k,b=p;
Exgcd(a,b,x,y);
x=(x%b+b)%b;
if(!x)x+=b;
return 1ll*x;
}
inline ll mul(ll n,ll p,ll pk)
//求n!%pi^ci,pk=pi^ci
{
if(!n)return 1;
ll ans=1;
for(ll i=2;i<=pk;i++)
if(i%p)ans=ans*i%pk;
ans=poww(ans,n/pk,pk);
for(ll i=2;i<=n%pk;i++)
if(i%p)ans=ans*i%pk;
return 1ll*ans*mul(n/p,p,pk)%pk;
//递归下去求解(n/pi)!%pi^ci
}
inline ll C(ll n,ll m,ll mod,ll p,ll pk)
//求C(n,m)%mod,其中唯一分解之后质因子为p,总乘积为pk(pi^ci)
{
if(m>n)return 0;
ll a=mul(n,p,pk),b=mul(m,p,pk),c=mul(n-m,p,pk),k=0;
//先求一下n!%pi^ci,m!%pi^ci,(n-m)!%pi^ci
for(ll i=n;i;i/=p)k+=i/p;
for(ll i=m;i;i/=p)k-=i/p;
for(ll i=n-m;i;i/=p)k-=i/p;
//先除掉n!,m!,(n-m)!在%mod下的质因子p
ll ans=1ll*a*rev(b,pk)%pk*rev(c,pk)%pk*poww(p,k,pk)%pk;
//除去质因子p之后直接逆元求组合数(剩余部分)
return 1ll*ans*(mod/pk)%mod*rev(mod/pk,pk)%mod;
//找到逆元了再乘回去(CRT合并)
}
int main()
{
/*这是我在做这个题的时候写的解释
思路:不妨设sum=∑wi(i:1~m)
题目很简单,就是要求式子:
C(n,sum)*C(sum,w1)*C(sum-w1,w2)*...*C(wi,wi)
但组合数要取模
自然想到逆元和Lucas定理
但是模数p不保证是质数,所以要用扩展Lucas
不妨先把p唯一分解,对于每一个pi^ci都两两互质
可以求出C(n,m)%pi^ci
对于求这个,除掉质因子pi然后求逆元
之后CRT一下乱搞就好啦
*/
mod=read(),n=read(),m=read();
for(int i=1;i<=m;i++)
A[i]=read(),sum+=A[i];
if(sum>n)//要送出的礼物多于有的礼物显然无解
{
printf("Impossible");
return 0;
}
for(ll k=1;k<=m;k++)//枚举每一个人要的礼物
{
n-=A[k-1];
ll now=0,x=mod;
for(ll i=2;i<=sqrt(mod);i++)
//找到mod的每一个质因数p
if(!(x%i))
{
ll pk=1;
while(!(x%i))pk*=i,x/=i;//除掉质因数p
now=(now+C(n,A[k],mod,i,pk))%mod;
//求出C(n,A[k])%pi^ci累加
}
if(x>1)now=(now+C(n,A[k],mod,x,x))%mod;
ans=ans*now%mod;//统计答案
}
printf("%lld",ans);//愉快的输出答案
return 0;
}
```
好了，到这里大概就讲完了吧= =
真香，又是一道毒瘤呢（逃
感谢阅读~~~
最后来推广一下我的blog:
https://www.luogu.org/blog/new2zy/
拜拜~~~ >=<