• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

qbxt五一数论Day3

开发技术 开发技术 1周前 (05-03) 7次浏览

1. 组合数取模

(dbinom nmbmod p)

1. (n,mle 200)(p) 任意

递推

2. (n,mle 10^6)(pge 10^9) 素数

预处理 (n!)(m!^{-1})((n-m)!^{-1}) 即可 .

3. (n,mle 10^6)(ple 2000) 素数

注意到 (n) 可能是 (p) 的倍数,故逆元可能不存在 .

引入 Lucas 定理:

(n,m)(p)(p) 是质数)进制下表示为

[overline{n_kn_{k-1}n_{k-2}dots n_1},,overline{m_km_{k-1}m_{k-2}dots m_1}
]

其中 (0le n_i<p)(0le m_i<p) .

则有:

[dbinom{n}{m}equiv dbinom{n_k}{m_k}dbinom{n_{k-1}}{m_{k-1}}cdotsdbinom{n_1}{m_1}pmod p
]

Proof:
原问题等价于 (C^n_mequiv C^{nbmod p}_{mbmod p}cdot C^{lfloor n/prfloor}_{lfloor m/prfloor}pmod p) .

(xinmathbb N^+),且 (x<p),则:

[C^x_p=dfrac{p!}{x!(p-x)!}=dfrac{pcdot (p-1)!}{xcdot(x-1)!cdot(p-x)!}=dfrac pxcdot C^{x-1}_{p-1}
]

由于 (x<p)(p) 是素数,所以 (x) 存在模 (p) 意义下的逆元,因此:

[C^x_pequiv pcdot x^{-1}cdot C^{x-1}_{p-1}pmod p
]

因为 (pcdot x^{-1}cdot C^{x-1}_{p-1}equiv 0pmod p) ,故 (C^x_pequiv0pmod p).

由二项式定理,

[(1+x)^p=sum_{i=0}^pC_p^ix_i
]

除了 (i=0,i=p) 的项数,别的模 (p) 均为 (0),所以:

[(1+x)^pequiv 1+x^ppmod p
]

现在我们设:

[begin{cases}lfloor m/prfloor=q_m\lfloor n/prfloor=q_nend{cases} , begin{cases}mbmod p=r_m\nbmod p=r_nend{cases}
]

从而:

[begin{cases}m=q_mp+r_m\n=q_np+r_nend{cases}
]

再由二项式定理有

[(1+x)^m=sum_{i=0}^mC_m^ix_i
]

而同时又有:

[begin{aligned}(1+x)^m&=(1+x)^{q_mp+r_m}\&=(1+x)^{q_mp}cdot(q+x)^{r_m}\&=((1+x)^q)^{m_p}cdot(q+x)^{r_m}\&equiv (1+x^p)^{q_m}cdot(1+x)^{r_m}\&=sum_{i=0}^{q_m}C^i_{q_m}x^{ip}sum_{i=0}^{r_m}C^i_{r_m}x^{i}\&=sum_{i=0}^{q_m}sum_{j=0}^{r_m}C^i_{q_m}C^j_{r_m}x^{ip+j}pmod pend{aligned}
]

注意到 (ip+j) 正好能取到 (0)(m) 内所有整数一次,所以枚举 (k=ip+j),得

[(x+1)^mequiv sum_{k=0}^n C_{q_m}^{lfloor k/prfloor}C_{r_m}^{kbmod p}x^kpmod p
]

结合二项式定理,得

[sum_{k=0}^mC^k_mx^kequiv sum_{k=0}^n C_{q_m}^{lfloor k/prfloor}C_{r_m}^{kbmod p}x^kpmod p
]

对比系数,得:

[C^n_mequiv C^{nbmod p}_{mbmod p}cdot C^{lfloor n/prfloor}_{lfloor m/prfloor}=C_{q_m}^{q_n}C_{r_m}^{r_n}pmod p
]

命题获证 .

4. (n,mle 10^6)(p=p_1p_2cdots p_k)(p_1,p_2,cdots,p_kle 2000) 为互不相同的素数

[A=dbinom nm
]

[begin{cases}Aequiv dbinom nmbmod p_1pmod p_1\Aequiv dbinom nmbmod p_2pmod p_2\cdots\Aequiv dbinom nmbmod p_kpmod p_kend{cases}
]

用 Lucas 定理求组合数,然后 CRT 合并即可


程序员灯塔
转载请注明原文链接:qbxt五一数论Day3
喜欢 (0)