bzoj2142 gift (extended Lucas+CRT)

Given n items and m people, each person gets wi gifts, and the number of solutions is not necessarily a prime number

First of all, we give the rest of the gifts to one person. The answer is obviously the same. w[++m]=n-w1-w2 - -wm
So the obvious answer is Cw1nCw2n − w1... Cwmn − w1 −... - wm − 1, that is, n!w1!w2!... wm!%P
What if P is not a prime number? Let's set P = Πi=1kpaii. Then we can calculate a remainder for each paii and get a system of modular linear equations. Then we can combine it with the Chinese remainder theorem. (because the two must be reciprocal, the common CRT is OK.)

Now our problem is how to calculate n!w1!w2!... wm!%paii. Because factorials may not be mutually prime with pi, there is no inverse element. gg. If we write the numerator and denominator in the form of xpki, then (x,pi)=1, we can calculate the inverse element. The power of the remaining pi can be directly reduced.

Let's consider how to calculate the part of mutual quality. Go to this typical example and you will: portal

I can't calculate the complexity anymore, qaq

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define ll long long
#define ld long double
#define inf 0x3f3f3f3f
#define N 110
inline char gc(){
    static char buf[1<<16],*S,*T;
    if(S==T){T=(S=buf)+fread(buf,1,1<<16,stdin);if(T==S) return EOF;}
    return *S++;
}
inline int read(){
    int x=0,f=1;char ch=gc();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc();
    return x*f;
}
int P,nn,w[10],m,prime[N],mo[N],r[N],sum=0,tot=0;
inline void decomp(){
    int x=P;
    for(int i=2;i*i<=P;++i){
        if(x%i) continue;prime[++tot]=i;mo[tot]=1;
        while(x%i==0) x/=i,mo[tot]*=i;
    }if(x!=1) prime[++tot]=x,mo[tot]=x;
}
inline void exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){x=1;y=0;return;}
    exgcd(b,a%b,x,y);ll t=x;x=y;y=t-a/b*y;
}
inline int ksm(ll x,int k,int mod){
    ll res=1;for(;k;k>>=1,x=x*x%mod) if(k&1) res=res*x%mod;return res;
}
inline int inv(int a,int mod){
    ll x,y;exgcd(a,mod,x,y);return (x%mod+mod)%mod;
}
inline int multi(int n,int p,int mod){//Calculate n!% mod coprime
    if(!n) return 1;ll res=1;
    for(int i=2;i<mod;++i) if(i%p) (res*=i)%=mod;
    res=ksm(res,n/mod,mod);
    for(int i=2;i<=n%mod;++i) if(i%p) (res*=i)%=mod;
    return res*multi(n/p,p,mod)%mod;
}
inline int calc(int n,int p,int mod){//n!/w1!w2!...wm! %mod
    ll res=multi(n,p,mod);
    for(int i=1;i<=m;++i){
        ll tmp=multi(w[i],p,mod);
        res=res*inv(tmp,mod)%mod;
    }int k=0;//Calculation of non reciprocal parts 
    for(ll i=p;i<=n;i*=p) k+=n/i;
    for(int i=1;i<=m;++i) for(ll j=p;j<=w[i];j*=p) k-=w[i]/j;
    return res*ksm(p,k,mod)%mod;
}
inline int CRT(int n,int mod){
    ll res=0;
    for(int i=1;i<=n;++i){
        ll a=P/mo[i],b=mo[i];
        res+=r[i]*a%mod*inv(a,b);res%=mod;
    }return res;
}
int main(){
//  freopen("a.in","r",stdin);
    P=read();nn=read();m=read();
    for(int i=1;i<=m;++i) w[i]=read(),sum+=w[i];
    if(sum>nn){puts("Impossible");return 0;}w[++m]=nn-sum;
    decomp();for(int i=1;i<=tot;++i) r[i]=calc(nn,prime[i],mo[i]);
    printf("%d\n",CRT(tot,P));
    return 0;
}

Tags: REST

Posted on Sat, 04 Apr 2020 14:02:08 -0700 by mitcho