扩展卢卡斯定理
最近光做模板了
想了解卢卡斯定理的去这里，那题也有我的题解
然而这题和卢卡斯定理并没有太大关系（雾
但是，首先要会的是中国剩余定理和exgcd
卢卡斯定理用于求\(n,m\)大，但模数\(p\)是质数，且较小的情况
但这题\(p\)并不保证是质数
所以，首先可以通过唯一分解定理给\(p\)分解乘若干质数相乘的形式：\(p=\prod p_i^{r_i}\)，当然\(r\)数列是分解后每个质数的指数
则我们可以对于每个\(p_i^{r_i}\)，求出\(\tbinom{n}{m} \bmod {p_i^{r_i}}\)，然后用crt进行合并，求出\(\tbinom{n}{m}\bmod p\)的值
所以，问题转化为：求\(\tbinom{n}{m} \bmod {p^{r}}\)，\(p\)为质数（为了写起来方便 下文中所有\(p\)实际上都表示的是上文的\(p_i\)，\(r\)表示\(r_i\)）
又由于\(\tbinom{n}{m}=\dfrac{n!}{m!(n-m)!}\)
所以可以把\(n!\)中，所有是\(n\)的倍数的项都提出来，让它们都除以\(p\)，然后就又得到了一个长度为\(\lfloor \dfrac{n}{p}\rfloor\)的从一开始的自然数数列，然后递归的求解\(\lfloor \dfrac{n}{k}\rfloor!\)
那么，对于不是\(n\)的倍数的项，可以发现，它们\(\bmod p^r\)的值以\(p^r\)为一个循环节，所以我们只要求出这个循环节内所有数相乘的积，然后做一个快速幂求它的\(\lfloor \dfrac{n}{k}\rfloor\)次方就行了
而对于\(n \bmod k\)个长度不足一个循环节的数，直接把它乘起来就行了
然后求\(n!\)中因数\(p\)出现的次数是很容易的（具体见代码），那么除法就对应减去\(p\)出现的次数
而剩下的数（也就是刚才把\(p\)除掉来求的）中不含\(p\)，可以求\(\bmod p^r\)的逆元，就也能进行除法
最后记得能开long long的一定开long long
一遍过超开心
写了一晚上+一早上有什么可开心的。。。
另外这题的数据好像有些水，具体看这个帖，也不知道加强了没有
所以可以去看一下礼物这个题，loj和bzoj上都有
那题知道这个算法以后思维难度几乎为0，就是求
然后这个礼物也成为了在洛谷A的第一个黑题虽然有些虚高
贴上代码
模板：
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<iomanip>
#include<cstring>
#define reg register
#define EN std::puts("")
#define LL long long
inline LL read(){
LL x=0,y=1;
char c=std::getchar();
while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
return y?x:-x;
}
LL n,m,p;
inline LL power(LL a,LL b,LL pr){
LL ret=1;
while(b){
if(b&1) ret=(ret*a)%pr;
b>>=1;a=(a*a)%pr;
}
return ret;
}
void exgcd(LL a,LL b,LL &x,LL &y){
if(!b) return x=1,y=0,void();
exgcd(b,a%b,x,y);
LL tmp=x;x=y;
y=tmp-a/b*y;
}
inline LL getinv(LL nn,LL mod){
LL x,y;
exgcd(nn,mod,x,y);
return (x+mod)%mod;
}
inline LL getfac(LL nn,LL pr,LL pp){//n!=x*p^y
if(!nn) return 1;
reg LL ans=1;
for(reg LL i=2;i<pr;i++)
if(i%pp) ans=ans*i%pr;
ans=power(ans,nn/pr,pr);
reg LL tmp=nn%pr;
for(reg LL i=2;i<=tmp;i++)
if(i%pp) ans=ans*i%pr;
return ans*getfac(nn/pp,pr,pp)%pr;
}
inline LL C(LL nn,LL mm,LL pp,LL pr){
LL x=getfac(nn,pr,pp),y=getfac(mm,pr,pp),z=getfac(nn-mm,pr,pp);
LL num=0;//计算因数种有几个p
for(reg LL i=nn;i;i/=pp) num+=i/pp;
for(reg LL i=mm;i;i/=pp) num-=i/pp;
for(reg LL i=nn-mm;i;i/=pp) num-=i/pp;
return x*getinv(y,pr)%pr*getinv(z,pr)%pr*power(pp,num,pr)%pr;
}
inline void crt(LL &ans,LL pr,LL ai){
ans=(ans+(getinv(p/pr,pr)*ai%p*(p/pr)%p))%p;//这里p/pr就相当于crt里的Mi
}
inline LL exlucas(){
LL ans=0,pp=p,pr,sqrt=std::sqrt(p);//pr=p^r
for(reg LL i=2;i<=sqrt;i++)if(!(pp%i)){
pr=1;
while(!(pp%i)) pp/=i,pr*=i;
crt(ans,pr,C(n,m,i,pr));
}
if(pp>1) crt(ans,pp,C(n,m,pp,pp));//还有因数
return ans;
}
int main(){
n=read();m=read();p=read();
std::printf("%lld",exlucas());
return 0;
}
礼物那题
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<iomanip>
#include<cstring>
#define reg register
#define EN std::puts("")
#define LL long long
inline LL read(){
LL x=0,y=1;
char c=std::getchar();
while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
return y?x:-x;
}
LL p;
inline LL power(LL a,LL b,LL pr){
LL ret=1;
while(b){
if(b&1) ret=(ret*a)%pr;
b>>=1;a=(a*a)%pr;
}
return ret;
}
void exgcd(LL a,LL b,LL &x,LL &y){
if(!b) return x=1,y=0,void();
exgcd(b,a%b,x,y);
LL tmp=x;x=y;
y=tmp-a/b*y;
}
inline LL getinv(LL nn,LL mod){
LL x,y;
exgcd(nn,mod,x,y);
return (x+mod)%mod;
}
inline LL getfac(LL nn,LL pr,LL pp){//n!=x*p^y
if(!nn) return 1;
reg LL ans=1;
for(reg LL i=2;i<pr;i++)
if(i%pp) ans=ans*i%pr;
ans=power(ans,nn/pr,pr);
reg LL tmp=nn%pr;
for(reg LL i=2;i<=tmp;i++)
if(i%pp) ans=ans*i%pr;
return ans*getfac(nn/pp,pr,pp)%pr;
}
inline LL C(LL nn,LL mm,LL pp,LL pr){
LL x=getfac(nn,pr,pp),y=getfac(mm,pr,pp),z=getfac(nn-mm,pr,pp);
LL num=0;//计算因数种有几个p
for(reg LL i=nn;i;i/=pp) num+=i/pp;
for(reg LL i=mm;i;i/=pp) num-=i/pp;
for(reg LL i=nn-mm;i;i/=pp) num-=i/pp;
return x*getinv(y,pr)%pr*getinv(z,pr)%pr*power(pp,num,pr)%pr;
}
inline void crt(LL &ans,LL pr,LL ai){
ans=(ans+(getinv(p/pr,pr)*ai%p*(p/pr)%p))%p;//这里p/pr就相当于crt里的Mi
}
inline LL exlucas(LL n,LL m){
LL ans=0,pp=p,pr,sqrt=std::sqrt(p);//pr=p^r
for(reg LL i=2;i<=sqrt;i++)if(!(pp%i)){
pr=1;
while(!(pp%i)) pp/=i,pr*=i;
crt(ans,pr,C(n,m,i,pr));
}
if(pp>1) crt(ans,pp,C(n,m,pp,pp));//还有因数
return ans;
}
LL w[10];
int main(){
p=read();LL n=read(),m=read();
LL sum=0;
for(reg int i=1;i<=m;i++) w[i]=read(),sum+=w[i];
if(sum>n) return std::puts("Impossible"),0;
LL ans=1;
for(reg int i=1;i<=m;i++){
ans=(ans*exlucas(n,w[i]))%p;
n-=w[i];
}
std::printf("%lld",ans);
return 0;
}