寫了個 TODO List，現在不會忘寫博客了
咕
# 題面
> Link DarkBZOJ 2142
\(n\) 件不同的禮物送給 \(m\) 個人，其中送給第 \(i\) 個人禮物數量為 \(w_i\)，計算出送禮物的方案數（兩個方案被認為是不同的，當且僅當存在某個人在這兩種方案中收到的禮物不同），由于方案數可能會很大，輸出模 \(P\) 后的結果，
設 \(P=p_1^{c_1}p_2^{c_2}\cdots p_t^{c_t}\)，\(p_i\) 為質數，則保證 \(p_i^{c_i}\le10^5\)，
# 決議
普通的 Lucas 定理只能用來求組合數模較小的素數的問題，
(部分) Lucas 定理
$$ \binom{n}{m}\bmod p=\binom{\lfloor\tfrac{n}{p}\rfloor}{\lfloor\tfrac{m}{p}\rfloor}\binom{n\bmod p}{m\bmod p}\bmod p $$
（但是似乎不是完整的 Lucas 定理？）
而 exLucas 定理可以解決 \(p\) 不是一個質數的問題（只要滿足「BZOJ 禮物」這道題對 \(p\) 的限制即可），
首先對 \(p\) 進行質因數分解 \(p=\prod\limits_{i=1}^tp_i^{c_i}\)，設 \(x=\binom{n}{m}\bmod p\)，\(x_i=\binom{n}{m}\bmod p_i^{c_i}\)，則
\[\begin{cases} x\equiv x_1\pmod{p_1^{c_1}}\\ x\equiv x_2\pmod{p_2^{c_2}}\\ \cdots\\ x\equiv x_t\pmod{p_t^{c_t}} \end{cases} \]模數互質，可以直接CRT，所以問題轉化為「組合數模一個質數的冪 \(p^k\)」，
把組合數的式子展開 \(\binom{n}{m}=\frac{n!}{m!(n-m)!}\)，我們不能直接求 \(m!\) 和 \((n-m)!\) 的逆元，因為它們不一定和 \(p\) 互質，于是想到，可以先把階乘中 \(p\) 的因子部分提出來，剩下的與 \(p\) 互質的部分就可以求逆元，即
\[m!=p^a\cdot b \]其中 \(p\not\mid b\)，\((n-m)!\) 同理，于是剩下的問題就是怎么將階乘分解成上述形式，
考慮計算 \(a\)：統計 \(1,2,\cdots,m\) 中能提取出多少 \(p\) 的因子，比較簡單，只需要對每個 \(p\) 的冪 \(p^i\) 統計 \(1\sim m\) 中有多少 \(p^i\) 的倍數，可以 \(O(\log_p m)\) 完成，
再考慮計算 \(b\)，可以遞回計算：
- 先計算出 \(1\sim m\) 中所有非 \(\mathbf{p}\) 的倍數的數之積模 \(p^k\)；
- 再將 \(p\) 的倍數單獨提出來，除以 \(p\) 后即為 \(1\sim\lfloor\tfrac{m}{p}\rfloor\)，遞回處理，
可以先預處理出 \(f_i\) 表示 \(1\sim i\) 中所有不為 \(p\) 的倍數的數的積模 \(p^k\)，則第一步的答案為
\[f_{p^k-1}^{\lfloor\frac{m}{p}\rfloor}\cdot f_{m\bmod p^k} \]現在就可以快速計算組合數了，
對于這道題，可以直接拆開組合數，計算
\[\frac{n!}{w_1!w_2!\cdots w_m!(n-w_1-w_2-\cdots-w_m)!} \]然后直接用 exLucas 的拆解階乘的方法，再用CRT合并（就不需要真的去計算每個組合數），
# 源代碼
點擊展開/折疊代碼
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long llong;
const int N=100,B=1e5+10;
#define con(type) const type &
int mul(con(int)a,con(int)b,con(int)mod){return int(1ll*a*b%mod);}
int ina_pow(con(int)a,con(llong)b,con(int)mod){return b?mul(ina_pow(mul(a,a,mod),b>>1,mod),(b&1)?a:1,mod):1;}
typedef pair<int,llong> pii;
int p[N],pc[N],fac[B],phi[N];
llong rem[N],w[N],mod;
int n,m,np;
void init(){
llong now=mod;
for(int i=2;1ll*i*i<=now;i++)
if(now%i==0){
p[++np]=i,pc[np]=1;
while(now%i==0) now/=i,pc[np]*=i;
}
if(now>1) np++,p[np]=pc[np]=(int)now;
for(int i=1;i<=np;i++) rem[i]=mod/pc[i],phi[i]=pc[i]/p[i]*(p[i]-1);
}
pii calc(con(llong)x,con(int)p0,con(int)pc0){
if(x<p0) return make_pair(fac[x],0);
pii res=calc(x/p0,p0,pc0);
return make_pair(mul(mul(res.first,fac[x%pc0],pc0),ina_pow(fac[pc0-1],x/pc0,pc0),pc0),res.second+x/p0);
}
int func(int p0,int pc0,int phi0){
fac[0]=1;
for(int i=1;i<pc0;i++) fac[i]=mul(fac[i-1],i%p0?i:1,pc0);
pii up=calc(n,p0,pc0);
fac[pc0-1]=ina_pow(fac[pc0-1],phi0-1,pc0);
for(int i=pc0-2;i;i--)
fac[i]=mul(fac[i+1],(i+1)%p0?i+1:1,pc0);
pii blw(1,0);
for(int i=1;i<=m;i++){
pii res=calc(w[i],p0,pc0);
blw.second+=res.second;
blw.first=mul(blw.first,res.first,pc0);
}
return mul(mul(up.first,blw.first,pc0),ina_pow(p0,up.second-blw.second,pc0),pc0);
}
int main(){
scanf("%lld%d%d",&mod,&n,&m);
init();
llong total=0;
for(int i=1;i<=m;i++){
scanf("%lld",&w[i]);
total+=w[i];
}
if(total>n){printf("Impossible\n");return 0;}
if(total<n) w[++m]+=n-total;
llong sum=0;
for(int i=1;i<=np;i++){
llong now=mul(func(p[i],pc[i],phi[i]),ina_pow(rem[i],phi[i]-1,pc[i]),mod);
now=mul(now,rem[i],mod);
sum=(sum+now)%mod;
}
printf("%lld\n",(sum%mod+mod)%mod);
return 0;
}
THE END
Thanks for reading!
史書缺失的那頁
遺忘了主角
有人傳說這一切
如流光幻夜
——《流光幻夜》By 司夏
> Link 流光幻夜-網易云
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/262409.html
標籤：其他
上一篇：「SOL」屠龍勇士(LOJ)