题解 P2183 【[国家集训队]礼物】

· · 题解

题解 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!= (1234678911…)5^(n/5)*(n/5)!

(乘号*没了555，变成了斜体请自行脑补)

那么我们直接提取出所有pi=5的倍数，正好分为三部分，直接按步骤上面计算就行了

其实以上就是(最恶心的)数论算法:扩展卢卡斯定理(ExLucas)

讲到这里。。。突然发现这东西好像和卢卡斯定理一点关系没有= =（所以Lucas不是必备的知识）

大概思路讲完了，我们在放代码之前可以来总结一下这次的求解方法，即扩展卢卡斯定理(ExLucas)

扩展卢卡斯定理适用于计算任意的C(n,m)%p问题，其中n,m,p为任意正整数

求解过程主要应用了乘法逆元（扩欧Exgcd求）、中国剩余定理(CRT也就只有一行)、带取模快速幂（码量很小）

总体来说思路还是很清楚的吧

那么好啦，既然有了解决方案，题目里的式子就很好求了吧，放个代码code~~~

PS:代码里也有解释哦

#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/

拜拜~~~ >=<