礼物
-
题意：
- 求$$C(n,m)\ %\ p$$
- \(n,m,p\le 10^9\)，且若\(p=\prod_{i=1}^{k}{p_i}^{c_i}\)，则\(\forall i\in [1..k]{p_i}^{c_i}\le 10^5.\)
注意到若$$p=\prod_{i=1}{k}{p_i}{c_i}，则\forall i\in [1..k]{p_i}^{c_i}\le 10^5.$$
于是有一个经典套路就是，求出\(k\)组\(A_i=C(n,m)\% {p_i}^{c_i}\)，最后用中国剩余定理求解.
注意到若中国剩余定理求出一组特解为\(Ans\)，则\((Ans+kp)\)为其通解.
由于\(p\)不保证为质数，所以我们需要对\(C(n,m)\)拆式子，然后把含\(p\)的与不含\(p\)的质因子分开算.
于是问题转化为求\(n!\)，我们以\(p^c\)个数为一组，不难发现，把含\(p\)质因子的数筛出去后每一组的乘积在模\(p^c\)意义下是一样的.
这个证明很显然，因为每一组都可以表示为\((k*p^c+1,k*p^c+2,\cdots,(k+1)*p^c)\).
于是发现含有\(p\)的质因子又是一个阶乘.
所以分治处理.
注意这里对于模数非质数的求逆元方法：
我们要求\(x\)关于\(m\)的逆元，实质上就是\(ax + km = 1\)的解.
然后我们可以求得这个\(a\)，用拓展\(gcd\)即可.
ll Exgcd(L a, L b, L &x, L &y) {
if (!b) { x = 1, y = 0; return a; }
L d = Exgcd(b, a % b, x, y), z = x;
x = y, y = z - y * (a / b); return d;
} //拓欧
ll CALC(L st, L en, L k) { L s = 1;
F(i, st, en) if (i % sta[k].p) s = (s * i) % sta[k].up;
return s;
}
ll calc(L n, L k) {
if (n <= sta[k].p) return CALC(1, n, k);
L k1 = calc(n / sta[k].p, k); //分治求解
L k2 = CALC(1, min(sta[k].up - 1, n), k); //每sta[k].up个分一组，这是一个循环节
if (n > sta[k].up) {
L k3 = CALC((n / sta[k].up) * sta[k].up + 1, n, k); //计算循环节余剩的
return (k1 * ksm(k2, n / sta[k].up, sta[k].up) * k3) % sta[k].up;
}
else return (k1 * k2) % sta[k].up;
}
ll count(L n, L p) { return n < p ? 0 : n / p + count(n / p, p); } //分治计算含p质因子个数
ll Inv(L t, L p) {
L d, x, y; d = Exgcd(t, p, x, y); //求逆元
return (x % p + p) % p;
}
ll C(L x, L y) {
L ss = 0;
F(i, 1, cnt) {
L s1 = calc(x, i), s2 = (calc(y, i) * calc(x - y, i)) % sta[i].up, tot; //计算x!/y!(x-y)!
s1 = s1 * Inv(s2, sta[i].up) % sta[i].up; //与sta[i].up互质，所以用拓欧求逆元.
tot = count(x, sta[i].p) - count(y, sta[i].p) - count(x - y, sta[i].p); //计算含p质因子个数
s1 = s1 * ksm(sta[i].p, tot, sta[i].up) % sta[i].up; //快速幂一下
G[i] = {s1, sta[i].up}; //一组方程
}
F(i, 1, cnt) {
L Mi = p / sta[i].up;
ss = (ss + ((G[i].a * Mi % p) * Inv(Mi, G[i].mo))) % p; //构造一组特解
}
return ss == 0 ? p : (ss % p + p) % p; //通解
}
- 此题是很好的思维+数论模板题.