题目描述

Dr. Ceizenp’ok from planet i1c5l became famous across the whole Universe thanks to his recent discovery – the Ceizenpok’s formula. This formula has only three arguments: $n, k$ and $m$, and its value is a number of $k$-combinations of a set of $n$ modulo $m$.
While the whole Universe is trying to guess what the formula is useful for, we need to automate its calculation.

算法分析

$$x={n \choose k}, \; m=p_1^{a_1}p_2^{a_2} \cdots p_q^{a_q}$$

$$\left\{ \begin{array}{c} x \equiv r_1 \pmod{p_1^{a_1}} \\ x \equiv r_2 \pmod{p_2^{a_2}} \\ \cdots \\ x \equiv r_q \pmod{p_q^{a_q}} \end{array} \right.$$

$${n \choose k}={n! \over k!(n-k)!}$$

$$f(n)=n! \bmod p_i^{a_i}$$

$$f(n)=\left(f\left(\left\lfloor{n \over p_i}\right\rfloor\right)\cdot p_i^{\lfloor n/p_i \rfloor}\cdot\left(\prod_{i \in [1, p_i^{a_i}], \; p_i\not\mid i}i\right)^{\lfloor n/p_i^{a_i} \rfloor}\cdot\prod_{i \in [1, n \bmod p_i^{a_i}], \; p_i\not\mid i}i\right)\bmod p_i^{a_i}$$

代码

/*
* Your lucky number has been disconnected.
*/

#include <algorithm>
#include <cstdio>
#include <cstring>

#define int long long

int power(int a, int b, int m) {
int ret = 1;
for (; b; b >>= 1)
b & 1 && ((ret *= a) %= m), (a *= a) %= m;
return ret;
}

void ex_gcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1, y = 0;
return;
}
ex_gcd(b, a % b, y, x), y -= a / b * x;
}

int get_inv(int a, int b) {
int x, y;
ex_gcd(a, b, x, y);
return (x + b) % b;
}

int get_fac(int n, int p, int k) {
int m = power(p, k, 1e9), ret = 1;
for (; n; n /= p) {
if (n / m) {
int rec = 1;
for (int i = 2; i < m; ++i)
if (i % p)
(rec *= i) %= m;
(ret *= power(rec, n / m, m)) %= m;
}
for (int i = n % m; i > 1; --i)
if (i % p)
(ret *= i) %= m;
}
return ret;
}

int calc(int N, int K, int M, int p, int k) {
int a = get_fac(N, p, k), b = get_fac(K, p, k), c = get_fac(N - K, p, k),
cnt = 0;
for (int i = N; i; i /= p)
cnt += i / p;
for (int i = K; i; i /= p)
cnt -= i / p;
for (int i = N - K; i; i /= p)
cnt -= i / p;
int m = power(p, k, 1e9),
ret = a * get_inv(b, m) % m * get_inv(c, m) % m * power(p, cnt, m) % m;
return ret * (M / m) % M * get_inv(M / m, m) % M;
}

signed main() {
int N, K, M, ans = 0;
scanf("%lld%lld%lld", &N, &K, &M);
for (int i = 2, t = M; t > 1; ++i)
if (!(t % i)) {
int k = 0;
for (; !(t % i); ++k, t /= i)
;
(ans += calc(N, K, M, i, k)) %= M;
}
printf("%lld\n", ans);
return 0;
}


Notes on Module

逆元

$$(a/(a, m))x \equiv b/(a, m) \pmod {m/(a, m)}$$

$$x \equiv (a/(a, m))^{-1} \times (b/(a, m)) \pmod {m/(a, m)}$$

$$x \equiv (a/(a, m))^{-1} \times (b/(a, m)) + (m/(a, m)) \times k \pmod m \; (0 \le k \lt (a, m))$$

费马小定理

\begin{align} x^{p-1} &\equiv 1 \pmod p \\ x^{-1} &\equiv x^{p-2} \pmod p \end{align}

$$x^{\varphi(m)} \equiv 1 \pmod m$$

线性同余方程组

\left\{ \begin{align} x &\equiv b_i \pmod {m_i} \\ ax &\equiv b_{i+1} \pmod {m_{i+1}} \end{align} \right.

$$a(tm_i+b_i) \equiv b_{i+1} \pmod {m_{i+1}}$$

$$atm_i \equiv b_{i+1}-ab_i \pmod {m_{i+1}}$$

中国剩余定理

$$\forall i \in [1, n], \; a_i=1 \land \forall i, j \in [1, n] \land i \neq j, \; (m_i, m_j)=1$$

$$x \equiv b \pmod {\prod m_i}$$

\begin{align} (a, b)\times(c, d)&=(ac, b+d) \\ (a, b)/(c, d)&=(ac^{-1}, b-d) \end{align}

$n!$

$$((p-1)!)^{n/p} \times (n \bmod p)!$$

${n \choose k} \bmod p$

$$n=\sum n_ip^i \; (0 \le n_i \lt p), \; k=\sum k_ip^i \; (0 \le k_i \lt p)$$

$${n \choose k} \equiv \prod {n_i \choose k_i} \pmod p$$

$${n \choose k}={n! \over k!(n-k)!}$$

$$n!=a_1p^{e_1}, \; k!=a_2p^{e_2}, \; (n-k)!=a_3p^{e_3}$$

Notes on Math Theory

Lucas

$n=(a_ka_{k-1}a_{k-2}\ldots a_0)_p, \; m=(b_kb_{k-1}b_{k-2}\ldots b_0)_p, \; {n \choose m} \equiv \prod_{i=0}^k {a_i \choose b_i} \pmod p$.
$n!$中$p$的次数$=\sum_{i=1}^{\infty} [{n \over p^i}]={n-S_p(n) \over p-1}$
${n \choose m}$中$p$的次数$p^\alpha \mid \mid {n \choose m} \Leftrightarrow p^\alpha \mid {n \choose m} \land p^{\alpha+1} \not \mid {n \choose m}$.
${n \choose m} \rightarrow p \not \mid {n \choose m} \Leftrightarrow {n-S_p(n) \over p-1}={m-S_p(m) \over p-1}+{n-m-S_(n-m) \over p-1} \Leftrightarrow m+(n-m)$在$p$进制下无进位。
$(1+x)^n \rightarrow x^m$系数${n \choose m}$.
$(1+x)^{p^k} \equiv 1+x^{p^k} \pmod p$.
$(1+x)^{a_kp^k+ \cdots +a_1p+a_0}=(1+x)^{a_kp^k} \cdots (1+x)^{a_1p}(1+x)^{a_0}$.
$\equiv (1+x^{p^k})^{a_k} \cdots (1+x^p)^{a_1}(1+x)^{a_0} \pmod p$.
$n!!=1 \times 3 \times 5 \times \cdots \times n$.

Euler

$x^{\varphi(n)} \equiv 1 \pmod n, (x, n)=1$.
$x^n \equiv x^{n-\varphi(n)} \pmod n$.
$\bmod n$缩系.
$a_1 \times a_2 \times \cdots \times a_{\varphi(n)} \equiv a_1x \times a_2x \times \cdots \times a_{\varphi(n)}x \pmod n$.
$n$为素数，$x^{p-1} \equiv 1 \pmod p, p \not \mid x$.
$x^p \equiv x \pmod p$.
$\sum_{d \mid n} \varphi(d)=n$.
$\varphi(p^{\alpha})=p^{\alpha}-p^{\alpha-1}$.
$n=p_1^{\alpha_1} \cdots p_k^{\alpha_k}$.
$\sum_{\beta_i \le \alpha_i} \varphi(p_1^{\beta_1} \cdots p_k^{\beta_k})=\sum_{\beta_i \le \alpha_i} \prod_{i=1}^k \varphi(p_i^{\beta_i})=\prod_{i=1}^k \sum_{\beta_i \le \alpha_i} \varphi(p_i^{\beta_i})=\prod p_i^{\alpha_i}$.

$n=1$成立。
$n>1$时，设$p$为$n$最小的素因子。

$\begin{cases} p \mid 2^n-1\\ p \mid 2^{p-1}-1\\ p \mid 2^d-1 \end{cases} \Rightarrow \begin{cases} d \mid n\\ d \mid p-1 \end{cases} \Rightarrow d=1 \Rightarrow p \mid 1 \Rightarrow n=1$.
$ax+by=(a, b)$.
$nx+(p-1)y=(n, p-1)$.
$p \mid 2^{(n, p-1)}-1$.
∵$(n, p-1)=1$.
∴$p \mid 1$.

$1, x, x^2, \ldots, x^{\varphi(n)-1}$构成$\bmod n$的缩系，则称$x$为$n$的原根，记作$g$。
$p$是素数时，${g, g^2, \ldots, g^{p-1}} \equiv {1, 2, \ldots, p-1} \pmod p$.
$n$的原根有$\varphi(\varphi(n))$个。

${1, 2, \ldots, p-1} \Rightarrow {a, 2a, \ldots, (p-1)a}$.
$\sum i^k \equiv \sum (a_i)^k \Rightarrow (a^k-1) \sum i^k \equiv 0 \pmod p$.

二项同余式

$x^k \equiv n \pmod p$无解或有$(k, p-1)$个解。
$f(x) \equiv 0 \pmod p$.
$x^k \equiv 1 \pmod 1$有$d$个解，$d=(k, p-1)=ak+b(p-1)$。
$\begin{cases} x^{p-1} \equiv 1 \pmod p\\ x^k \equiv 1 \pmod 1 \end{cases} \Rightarrow x^{(k, p-1)} \equiv 1 \pmod p$至多$d$个解。
${x^{p-1}-1 \over x^d-1}=x^{p-1-d}+x^{p-1-2d}+ \cdots +x^d+1 \equiv 1 \pmod p$至多$p-1-d$个解。
$x^k \equiv 1 \pmod 1$恰有$d$个解。
$x \rightarrow p$的缩系，$x^k$有${p-1 \over (k, p-1)}$个不同的取值。
$x^{p-1} \equiv 1 \pmod p$且$x^d \not \equiv 1 \pmod p, d \lt p-1$，$x$是原根。

$x^{q^{\alpha}} \equiv 1 \pmod p$.
$x^{q^{\alpha-1}} \not \equiv 1 \Leftrightarrow \forall d \lt q^{alpha}, \; x^d \not \equiv 1 \pmod p$.
$x^{(q^{\alpha}, d)} \equiv 1 \Leftrightarrow x^{q^{\beta}} \equiv 1 \pmod p$.
$\gamma(l_1l_2)=\gamma(l_1)\gamma(l_2)$.
$h_1$次数是$l_1$，$h_2$次数是$l_2 \Rightarrow h_1h_2$的次数是$l_1l_2$。
$x$次数是$l_1l_2 \Rightarrow x_1$次数是$l_1$，$x_2$次数是$l_2$。

Prime

$\lim \sum_{p=1}^{\infty} (1-{1 \over p})=0$.

$f(x) \equiv 0 \pmod {p^{\alpha}}$的解数$=f(x) \equiv 0 \pmod p$的解数$\Leftarrow \begin{cases} f(x) \equiv 0\\ f'(x) \equiv 0 \end{cases} \pmod p$无解。
$x^2+1 \equiv 0 \pmod {p^{\alpha}}, p \ge 3$无解或恰有$2$解。

勾股数的通式

$a^2+b^2=c^2 (a, b, c \gt 0)$.
$(a, b, c)=1$本原。
$a^2+b^2=c^2 \Rightarrow b^2=c^2-a^2=(c-a)(c+a)$.
$(c-a, c+a)=(2c, c-a)=(2, c-a)=1$.
$2 \not \mid c-a$.

$\begin{cases} {c-a \over 2}=m^2\\ {c+a \over 2}=n^2 \end{cases}$.
$\begin{cases} b=2mn\\ a=n^2-m^2\\ c=n^2+m^2 \end{cases}$.

有理根 Eisenstein

$f \in Z[x], f(x)=a_nx^n+ \cdots +a_1x+a_0$.
$\pm {p \over q} \Rightarrow p \mid a_n, q \mid a_0$.
$f(x)=c_nx^n+c_{n-1}x^{n-1}+ \cdots +c_1x+c_0$可约$\Leftarrow p \mid c_0, p \mid c_1, \ldots, p \mid c_{n-1}, p \not \mid c_n, p^2 \not \mid c_0$.
$f(x)=c_nx^n+c_{n-1}x^{n-1}+ \cdots +c_1x+c_0$可约$\Leftarrow p \mid (c_0, c_1, \ldots, c_{n-1}), p \not \mid c_n, p^2 \not \mid c_0$.
$f(x)=x^{p-1}+x^{p-2}+ \cdots +x+1={x^p-1 \over {x-1}}$.

升幂定理

$5^{210000}-2^{210000}$里有多少$3$的幂次。$2$次。
$(1+p)^k-1$里有多少$p$的幂次。$1+V_p(k)$次。
$5^{33333}+1$里有多少$3$的幂次。$2$次。
$p^{\alpha} \mid \mid a-b, (a, p)=1, (b, p)=1, p \ge 3$.
$V_p(a^m-b^m)=\alpha+V_p(m)$.

$p^{\alpha} \mid \mid a^{pn}-b^{pn}$.
$p^{\alpha} \mid \mid a^{kn}-b^{kn}, (k, p)=1$.

二次剩余

$ax^2+bx+c \equiv 0 \pmod p$.
$x^2 \equiv a \pmod p$.

${p-1 \over (2, p-1)}={p-1 \over 2}$.
$1^2, 2^2, 3^2, \ldots, ({p-1 \over 2})^2$.

Euler判别法：$n^{p-1 \over 2} \equiv ({n \over p}) \pmod p, (n, p)=1$.
Gauss Lama：$n, 2n, 3n, \ldots, {p-1 \over 2}n \pmod p$的最小正剩余中大于${p-1 \over 2}$的个数为$m$，则$({n \over p})=(-1)^m$。
$({2 \over p})=(-1)^{p^2-1 \over 8}=(-1)^{[{p \over 2}]-[{p \over 4}]}$.

Summary

$n=(a_ka_{k-1}a_{k-2}\ldots a_0)_p, m=(b_kb_{k-1}b_{k-2}\ldots b_0)_p, {n \choose m} \equiv \prod_{i=0}^k {a_i \choose b_i} \pmod p$.

$x^{\varphi(n)} \equiv 1 \pmod n, (x, n)=1$.
$x^n \equiv x^{n-\varphi(n)} \pmod n$.
$n$为素数，$x^{p-1} \equiv 1 \pmod p, p \not \mid x$.
$x^p \equiv x \pmod p$.

$x^k \equiv n \pmod p$无解或有$(k, p-1)$个解。
$x^k \equiv 1 \pmod 1$有$d$个解，$d=(k, p-1)=ak+b(p-1)$。
$x \Rightarrow p$的缩系，$x^k$有${p-1 \over (k, p-1)}$个不同的取值。
$\bmod p$的原根有$\varphi(p-1)$个。

$\lim \sum_{p=1}^{\infty} (1-{1 \over p})=0$.

$f(x) \equiv 0 \pmod {p^{\alpha}}$的解数$=f(x) \equiv 0 \pmod p$的解数$\Leftarrow \begin{cases} f(x) \equiv 0\\ f'(x) \equiv 0 \end{cases} \pmod p$无解。

$\begin{cases} b=2mn\\ a=n^2-m^2\\ c=n^2+m^2 \end{cases}$.

$f(x)=c_nx^n+c_{n-1}x^{n-1}+ \cdots +c_1x+c_0$可约$\Leftarrow p \mid c_0, p \mid c_1, \ldots, p \mid c_{n-1}, p \not \mid c_n, p^2 \not \mid c_0$.
$f(x)=c_nx^n+c_{n-1}x^{n-1}+ \cdots +c_1x+c_0$可约$\Leftarrow p \mid (c_0, c_1, \ldots, c_{n-1}), p \not \mid c_n, p^2 \not \mid c_0$.

$p^{\alpha} \mid \mid a-b, (a, p)=1, (b, p)=1, p \ge 3$.
$V_p(a^m-b^m)=\alpha+V_p(m)$.