exLucas学习笔记

Tags：数学

---

写下抛硬币和超能粒子炮改

洛谷模板代码如下

#include<iostream>

#define ll long long

using namespace std;

void exgcd(int a,int b,int &x,int &y)

{

    if(b==0) {x=1;y=0;return;}

    exgcd(b,a%b,y,x);y-=a/b*x;

}

struct ex_lucas

{

    int p,pk,jc[1000001];

    void init()

        {

            for(int i=jc[0]=1;i<=pk;i++)

                jc[i]=1ll*jc[i-1]*(i%p?i:1)%pk;

        }

    int ksm(int x,ll k)

        {

            int s=1;for(;k;k>>=1,x=1ll*x*x%pk)

                        if(k&1) s=1ll*s*x%pk;return s;

        }

    int inv(int a)

        {

            int x,y;exgcd(a,pk,x,y);

            x=(x%pk+pk)%pk;return x;

        }

    int mul(ll n)

        {

            int s=1;

            for(;n;n/=p) s=1ll*s*ksm(jc[pk],n/pk)%pk*jc[n%pk]%pk;

            return s;

        }

    void Getp(ll n,int op,int &k) {for(;n;n/=p) k+=op*n/p;}

    int C(ll n,ll m)

        {

            int a=mul(n),b=mul(m),c=mul(n-m),k=0;

            Getp(n,1,k);Getp(m,-1,k);Getp(n-m,-1,k);

            return 1ll*a*inv(b)%pk*inv(c)%pk*ksm(p,k)%pk;

        }

}a[10];

ll n,m,p,x,tt,ans,A[11],B[11];

int exCRT()

{

    int P=A[1],R=B[1];

    for(int i=2;i<=tt;i++)

    {

        int x,y,np=A[i]*P;exgcd(P,A[i],x,y);

        x=(1ll*x*(B[i]-R)%np+np)%np;

        R=(1ll*x*P%np+R+np)%np;P=np;

    }

    return R;

}

int main()

{

    cin>>n>>m>>p;x=p;

    for(int i=2;i*i<=x;i++)

        if(x%i==0)

        {

            a[++tt].p=i;a[tt].pk=1;

            while(x%i==0) a[tt].pk*=i,x/=i;

        }

    if(x>1) ++tt,a[tt].p=a[tt].pk=x;

    for(int i=1;i<=tt;i++)

        a[i].init(),B[i]=a[i].C(n,m),A[i]=a[i].pk;

    ans=exCRT();

    cout<<ans<<endl;

}