╰(￣▽￣)╭

给定方程 X1+X 2+…+Xn=m 我们对第 1.. n1 个变量 进行一些限制 ： X1≤A1 X2≤A2 … Xn1 ≤An1 我们对第 n1+1.. n1+1.. n1+ n2 个变量 进行一些限制 ： X_(n1+1)≥A_(n1+1) X_(n1+2)≥A_(n1+2) … X_(n1+n2) ≥A_(n1+n2) 求：在满足这些限制的前提下， 该方程正整数解的个数。 答案可能很大，请输出对 p取模 后的答案 ，也即 答案除以 p的余数。

(⊙ ▽ ⊙)

利用容斥原理，可以将所有要满足的条件一转化为条件二。 而条件二可以利用隔板法，Ans=Cn−1m−1−∑xi$Ans=C_{m-1-/sum x_i}^{n-1}$。

但是，本道题的最大Trick是组合数取模：Lucas定理+中国剩余定理

两个定理

中国剩余定理

内容： 设a1,a2,a3...ak$a_1,a_2,a_3...a_k$两两互质，且一个数X mod$X/ mod$这些数，分别得到m1,m2,m3...,mk$m_1,m_2,m_3...,m_k$。 设Mj=∏ni=1mi(i!=j)$M_j=/<a href="http://pr.VeVb.com/">PR</a>od_{i=1}^nm_i(i!=j)$， 则X=∏ni=1ai∗Mi∗M−1i$X=/prod_{i=1}^na_i*M_i*M_i^{-1}$。

Lucas定理

内容： 举个例子，比如说要算19! mod 32$19!/ mod/ 3^2$。 19!=1∗2∗3∗4∗...∗19$19!=1*2*3*4*...*19$ 把所有3$3$的倍数提取出来： 19!=(1∗2∗4∗5∗7∗8∗10∗11∗13∗14∗16∗17∗19)∗36∗(1∗2∗3∗4∗5∗6)$19!=(1*2*4*5*7*8*10*11*13*14*16*17*19)*3^6*(1*2*3*4*5*6)$ 很显然，(1∗2∗3∗4∗5∗6)$(1*2*3*4*5*6)$可以利用相同的办法算出， (1∗2∗4∗5∗7∗8∗10∗11∗13∗14∗16∗17∗19)$(1*2*4*5*7*8*10*11*13*14*16*17*19)$则可以发现， 每32$3^2$属于一个循环节，于是可以使用快速幂优化。

为了可以使用中国剩余定理， 我们先对题目所给的模数p$p$分解质因数，得∏pkii$/prod p_i^{k_i}$。 对于Cmn$C^m_n$，要对p$p$取模； 就让它先对每个pkii$p_i^{k_i}$取模，这样就可以使用中国剩余定理。

问题又变成：Cmn$C^m_n$对pk$p^k$取模了， Cmn=n!m!(n−m!)$C^m_n=/frac{n!}{m!(n-m!)}$， 所以可以对n!,m!,(n−m)!$n!,m!,(n-m)!$分别使用Lucas定理： n!⇒t1∗pu1$n!⇒t1*p^{u1}$ m!⇒t2∗pu2$m!⇒t2*p^{u2}$ (n−m)!⇒t3∗pu3$(n-m)!⇒t3*p^{u3}$； 最后，模出来的数即为pu1−u2−u3∗t1∗t2−1∗t3−1$p^{u1-u2-u3}*t1*t2^{-1}*t3^{-1}$。

(￣～￣)

(⊙v⊙)

1.使用Lucas定理时，可以预处理阶乘； 2.使用Lucas定理时，要另开变量存储循环节的快速幂。