Clever Y

题目描述

Little Y finds there is a very interesting formula in mathematics:
$$
X^Y \bmod Z=K
$$
Given $X, Y, Z$, we all know how to figure out $K$ fast. However, given $X, Z, K$, could you figure out $Y$ fast?

题意概述

给定$X, Z, K$,求满足$X^Y \bmod Z=K$的$Y$的最小值。若不存在$0 \le Y \lt Z$满足条件,则输出无解。
数据范围:$0 \le X, Z, K \le 10^9$。

算法分析

显然$K \ge Z$时无解。在其他情况下,条件可以写成
$$
X^Y \equiv K \pmod Z
$$
特殊处理两种情况:$X, K$中至少有一个为$0$时,$Y=1$或无解;$K=1$时,$Y=0$。
先考虑$(X, Z)=1$的情况。令$M=\lceil \sqrt{Z} \rceil, \; Y=aM-b \; (0 \lt a, b \le M)$,那么
$$
\begin{align}
X^{aM-b} &\equiv K \pmod Z \\
X^{aM} &\equiv K \cdot X^b \pmod Z
\end{align}
$$
可以在$O(M)$的时间内预处理出$K \cdot X^b$,存在哈希表中,接着$O(M)$枚举$a$,判断哈希表中是否存在$X^{aM}$,若存在,则找到解$Y=aM-b$。由于要求最小值,因此哈希表中有重复时应记录较大的$b$。
下面考虑$(X, Z) \gt 1$的情况。令$D=(X, Z)$,易知若$K \nmid D$则无解。设$X=Dx, \; K=Dk, \; Z=Dz$,据同余的性质可得
$$
\begin{align}
(Dx)^Y &\equiv Dk \pmod{Dz} \\
x \cdot (Dx)^{Y-1} &\equiv k \pmod z
\end{align}
$$
因为$D=(X, Z)$,所以$(x, z)=1$,即$x$在模$z$意义下有逆元,因此
$$
(Dx)^{Y-1} \equiv k \cdot x^{-1} \pmod z
$$
令$X’=Dx=X, \; Y’=Y-1, \; K’=k \cdot x^{-1}, \; Z’=z$,则
$$
(X’)^{Y’} \equiv K’ \pmod{Z’}
$$
这和初始时的方程具有一样的形式。若$(X’, Z’) \gt 1$,则重复以上过程,否则可以参照$(X, Z)=1$的情况。

代码

/*
 * You will be singled out for promotion in your work.
 */

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

class HashTable {
private:
  static int const MOD = 3214567;
  int numr, h[MOD], id[MOD], val[MOD], nxt[MOD];

public:
  void clear() { memset(h, numr = 0, sizeof h); }

int count(int const &n) {
    for (int i = h[n % MOD]; i; i = i[nxt])
      if (i[id] == n)
        return 1;
    return 0;
  }

int &operator[](int const &n) {
    for (int i = h[n % MOD]; i; i = i[nxt])
      if (i[id] == n)
        return i[val];
    ++numr, numr[id] = n, numr[nxt] = h[n % MOD], h[n % MOD] = numr;
    return numr[val];
  }
} mp;

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

int get_gcd(int a, int b) {
  int x, y;
  return ex_gcd(a, b, x, y);
}

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

int bsgs(int a, int b, int c) {
  a %= c;
  if (a == 0)
    return b == 0 ? 1 : -1;
  if (b == 0)
    return -1;
  if (b == 1)
    return 0;
  int k = 0;
  for (int t; (t = get_gcd(a, c)) > 1; ++k) {
    if (b % t)
      return -1;
    c /= t, b /= t, b = 1ll * b * get_inv(a / t, c) % c;
  }
  mp.clear();
  int d = a, m = sqrt(c) + 1;
  for (int i = 1; i <= m; ++i, d = 1ll * d * a % c)
    mp[1ll * d * b % c] = i;
  d = 1ll * d * get_inv(a, c) % c;
  int e = d;
  for (int i = 1; i <= m; ++i, e = 1ll * e * d % c)
    if (mp.count(e))
      return i * m - mp[e] + k;
  return -1;
}

int main() {
  for (int a, b, c; scanf("%d%d%d", &a, &c, &b), a || b || c;) {
    int ans = bsgs(a, b, c);
    if (~ans)
      printf("%d\n", ans);
    else
      puts("No Solution");
  }
  return 0;
}

Ceizenpok’s Formula

题目描述

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.

题意概述

求${n \choose k} \bmod m$。
数据范围:$1 \le n \le 10^{18}, \; 0 \le k \le n, \; 2 \le m \le 10^6$。

算法分析


$$
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.
$$
由于模数两两互质,所以该方程组在模$m$意义下有唯一解。
考虑如何求$r_i$。实际上,我们要求的就是${n \choose k} \bmod p_i^{a_i}$。我们知道
$$
{n \choose k}={n! \over k!(n-k)!}
$$
那么只要求出$n! \bmod p_i^{a_i}, \; k! \bmod p_i^{a_i}, \; (n-k)! \bmod p_i^{a_i}$的值,就可以用逆元求出${n \choose k} \bmod p_i^{a_i}$。
对于如何求$n! \bmod p_i^{a_i}$,令
$$
f(n)=n! \bmod p_i^{a_i}
$$
由$x \equiv x+p_i^{a_i} \pmod{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}
$$
但是$k!, \; (n-k)!$在模$p_i^{a_i}$意义下可能不存在逆元,因此需要将$n!, \; k!, \; (n-k)!$中的$p_i$因子提取出来,求出逆元后再乘回去。
这样就得到了所有$r_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;
}

Strange Way to Express Integers

题目描述

Elina is reading a book written by Rujia Liu, which introduces a strange way to express non-negative integers. The way is described as following:

  • Choose $k$ different positive integers $a_1, a_2, \ldots, a_k$. For some non-negative $m$, divide it by every $a_i$ to find the remainder $r_i$. If $a_1, a_2, \ldots, a_k$ are properly chosen, $m$ can be determined, then the pairs $(a_i, r_i)$ can be used to express $m$.

“It is easy to calculate the pairs from $m$,” said Elina. “But how can I find $m$ from the pairs?”
Since Elina is new to programming, this problem is too difficult for her. Can you help her?

题意概述

给定同余方程组
$$
\left\{
\begin{array}{c}
x \equiv r_1 \pmod{a_1} \\
x \equiv r_2 \pmod{a_2} \\
\cdots \\
x \equiv r_k \pmod{a_k}
\end{array}
\right.
$$
求$x$的最小非负整数解。
数据范围:所有输入输出均可以表示为64位整型。

算法分析

对于两个方程
$$
\begin{align}
x &\equiv r_1 \pmod{a_1} \\
x &\equiv r_2 \pmod{a_2}
\end{align}
$$
考虑将它们合并。易知
$$
x=r_1+k_1a_1=r_2+k_2a_2
$$
移项得
$$
k_1a_1=r_2-r_1+k_2a_2
$$
由贝祖定理可知,这个方程有整数解的充要条件为$(a_1, a_2) \mid r_2-r_1$。方程两边同时除以$(a_1, a_2)$
$$
\begin{align}
k_1{a_1 \over (a_1, a_2)}&={r_2-r_1 \over (a_1, a_2)}+k_2{a_2 \over (a_1, a_2)} \\
k_1{a_1 \over (a_1, a_2)} &\equiv {r_2-r_1 \over (a_1, a_2)} \pmod{{a_2 \over (a_1, a_2)}} \\
k_1 &\equiv \left( {a_1 \over (a_1, a_2)} \right)^{-1} \cdot {r_2-r_1 \over (a_1, a_2)} \pmod{{a_2 \over (a_1, a_2)}}
\end{align}
$$
将其代回$x=r_1+k_1a_1$,得
$$
x \equiv r_1+k_1a_1 \pmod{{a_1a_2 \over (a_1, a_2)}}
$$
至此已成功将两个方程合并为一个相同形式的方程。

代码

/*
 * Your life would be very empty if you had nothing to regret.
 */

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

#define int long long

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

int get_gcd(int a, int b) {
  int x, y;
  return ex_gcd(a, b, x, y);
}

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

signed main() {
  for (int k, a, r; ~scanf("%lld%lld%lld", &k, &a, &r);) {
    int flag = 0;
    for (int ai, ri; --k;) {
      scanf("%lld%lld", &ai, &ri);
      int gcd = get_gcd(a, ai);
      if ((r - ri) % gcd)
        flag = 1;
      r += get_inv(a / gcd, ai / gcd) * ((ri - r) / gcd) % (ai / gcd) * a;
      (a /= gcd) *= ai, ((r %= a) += a) %= a;
    }
    if (flag)
      puts("-1");
    else
      printf("%lld\n", r);
  }
  return 0;
}

The Child and Binary Tree

题目描述

Our child likes computer science very much, especially he likes binary trees.
Consider the sequence of $n$ distinct positive integers: $c_1, c_2, \ldots, c_n$. The child calls a vertex-weighted rooted binary tree good if and only if for every vertex $v$, the weight of $v$ is in the set ${c_1, c_2, \ldots, c_n}$. Also our child thinks that the weight of a vertex-weighted tree is the sum of all vertices’ weights.
Given an integer $m$, can you for all $s \; (1 \le s \le m)$ calculate the number of good vertex-weighted rooted binary trees with weight $s$? Please, check the samples for better understanding what trees are considered different.
We only want to know the answer modulo $998244353$ ($7 \times 17 \times 2^{23}+1$, a prime number).

题意概述

有$n$种点,每种点有无限个,第$i$种点的权值为$c_i$。定义一棵二叉树的权值等于它所有点的权值之和。求对于所有$s \in [1, m]$,权值为$s$的二叉树有几棵。两棵二叉树不同当且仅当它们左子树或右子树不同,或者根节点权值不同。
数据范围:$1 \le n, m, c_i \le 10^5$。

算法分析

令$f(x)$表示权值为$x$的二叉树个数,$F(x)$为其生成函数($F(x)=\sum_{i \ge 0} f(i)x^i$)。
令$C(x)$为给定$c$的集合的生成函数($C(x)=\sum_{i=1}^n x^{c_i}$)。
根据DP转移方程,易知
$$
f(x)=\sum_{w \in {c_1, c_2, \ldots, c_n}} \sum_{i=0}^{x-w} f(i)f(x-w-i)
$$

$$
F(x)=C(x)F(x)^2+1
$$
解得
$$
F(x)={1 \pm \sqrt{1-4C(x)} \over 2C(x)}={2 \over 1 \pm \sqrt{1-4C(x)}}
$$
显然,若取减号,则当$x$趋近$0$时分母为$0$,因此只能取加号。接着就是多项式开根和多项式求逆了。

  • 多项式求逆:
    求$GF \equiv 1 \pmod {x^n}$。

    假设已知$G_0F \equiv 1 \pmod {x^{\lceil n/2 \rceil}}$
    $G-G_0 \equiv 0 \pmod {x^{\lceil n/2 \rceil}}$
    $G^2-2GG_0+G_0^2 \equiv 0 \pmod {x^n}$
    $G-2G_0+G_0^2F \equiv 0 \pmod {x^n}$
    $G \equiv 2G_0-G_0^2F \pmod {x^n}$

  • 多项式开根:
    求$G^2 \equiv F \pmod {x^n}$。

    假设已知$G_0^2 \equiv F \pmod {x^{\lceil n/2 \rceil}}$
    $(G_0^2-F)^2 \equiv 0 \pmod {x^n}$
    $(G_0^2+F)^2 \equiv 4G_0^2F \pmod {x^n}$
    $\left({G_0^2+F \over 2G_0}\right)^2 \equiv F \pmod {x^n}$
    $G \equiv {G_0+G_0^{-1}F \over 2} \pmod {x^n}$

代码

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

static const int N = 500000;
static const int MOD = 998244353;
static const int G = 3;
static const int INV2 = 499122177;
int n, m, c[N], C[N], rev[N], wn[N], tmp[N], tmp2[N], tmp3[N];

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

void init(int &n) {
  int m = n << 1, l = 0;
  for (n = 1; n < m; n <<= 1, ++l)
    ;
  for (int i = 1; i < n; ++i)
    rev[i] = rev[i >> 1] >> 1 | (i & 1) << (l - 1);
}

void ntt(int *a, int n, bool inv) {
  for (int i = 0; i < n; ++i)
    if (i < rev[i])
      std::swap(a[i], a[rev[i]]);
  wn[0] = 1, wn[1] = power(G, (MOD - 1) / n);
  for (int i = 2; i < n >> 1; ++i)
    wn[i] = 1ll * wn[i - 1] * wn[1] % MOD;
  for (int i = 1; i < n; i <<= 1)
    for (int j = 0; j < n; j += i << 1)
      for (int k = 0; k < i; ++k) {
        int x = a[j + k], y = 1ll * wn[n / (i << 1) * k] * a[j + k + i] % MOD;
        a[j + k] = (x + y) % MOD, a[j + k + i] = (MOD + x - y) % MOD;
      }
  if (inv) {
    for (int i = 1; i < n >> 1; ++i)
      std::swap(a[i], a[n - i]);
    int rec = power(n, MOD - 2);
    for (int i = 0; i < n; ++i)
      a[i] = 1ll * a[i] * rec % MOD;
  }
}

void get_inv(int *f, int *g, int n) {
  if (n == 1)
    return void(g[0] = power(f[0], MOD - 2));
  int rec = n;
  get_inv(f, g, (n + 1) >> 1), init(n);
  for (int i = (rec + 1) >> 1; i < n; ++i)
    g[i] = 0;
  for (int i = 0; i < rec; ++i)
    tmp[i] = f[i];
  for (int i = rec; i < n; ++i)
    tmp[i] = 0;
  ntt(g, n, 0), ntt(tmp, n, 0);
  for (int i = 0; i < n; ++i)
    g[i] = 1ll * g[i] * (MOD + 2 - 1ll * g[i] * tmp[i] % MOD) % MOD;
  ntt(g, n, 1);
  for (int i = rec; i < n; ++i)
    g[i] = 0;
}

void get_sqrt(int *f, int *g, int n) {
  if (n == 1)
    return void(g[0] = 1);
  int rec = n;
  get_sqrt(f, g, (n + 1) >> 1);
  for (int i = 0; i<(n + 1)>> 1; ++i)
    tmp2[i] = g[i];
  for (int i = (n + 1) >> 1; i < n; ++i)
    tmp2[i] = 0;
  get_inv(tmp2, tmp3, n), init(n);
  for (int i = (rec + 1) >> 1; i < n; ++i)
    g[i] = 0;
  for (int i = 0; i < rec; ++i)
    tmp2[i] = f[i];
  for (int i = rec; i < n; ++i)
    tmp2[i] = 0;
  ntt(tmp2, n, 0), ntt(tmp3, n, 0);
  for (int i = 0; i < n; ++i)
    tmp3[i] = 1ll * tmp3[i] * tmp2[i] % MOD;
  ntt(tmp3, n, 1);
  for (int i = 0; i < rec; ++i)
    g[i] = 1ll * (g[i] + tmp3[i]) * INV2 % MOD;
  for (int i = rec; i < n; ++i)
    g[i] = 0;
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; ++i)
    scanf("%d", &c[i]);
  for (int i = 0; i < n; ++i)
    if (c[i] <= m)
      ++C[c[i]];
  for (int i = 1; i <= m; ++i)
    C[i] = (MOD - (C[i] << 2)) % MOD;
  C[0] = 1;
  get_sqrt(C, c, m + 1), ++c[0], get_inv(c, C, m + 1);
  for (int i = 1; i <= m; ++i)
    printf("%d\n", (C[i] << 1) % MOD);
  return 0;
}

序列求和 V4

题意概述

给定$n$和$k$,求$\sum_{i=1}^n i^k \bmod 10^9+7$。有$T$组数据。
数据范围:$1 \le T \le 500, \; 1 \le n \le 10^{18}, \; 1 \le k \le 50000$。

算法分析1

设答案为$f(n)$。这是一个$(k+1)$次多项式,只要确定$(k+2)$个点就可以确定$f$。
我们可以令$x=1\ldots k+2$,在$O(k\log k)$时间内计算出它们对应的$y$。
利用拉格朗日插值法。假设有$n$个点$(x_i, y_i)$,那么
$$f(x)=\sum_{i=1}^n {\prod_{j \in [1, n] \land j \neq i} (x-x_j) \over \prod_{j \in [1, n] \land j \neq i} (x_i-x_j)}y_i$$
考虑分子部分。在给定$x$的情况下,这一部分可以$O(k)$预处理$O(1)$求值。
考虑分母部分。它形如$\prod_{j \in [i-k-2, i-1] \land j \neq 0} j$,可以在插值时$O(1)$维护。
总时间复杂度为$O(Tk\log k)$。

代码1

#include <cstdio>

#define int long long

void read(int &n) {
  char c; while ((c = getchar()) < '0' || c > '9') ; n = c - '0';
  while ((c = getchar()) >= '0' && c <= '9') (n *= 10) += c - '0';
}

static const int K = 50005;
static const int MOD = 1000000007;
int n, k, a[K], p[K], q[K], inv[K], base[K];

int power(int a, int b) {
  int ret = 1; a %= MOD, b %= MOD - 1;
  while (b) b & 1 && ((ret *= a) %= MOD), (a *= a) %= MOD, b >>= 1;
  return ret;
}

int calc(int n) {
  if (n <= k + 2) return a[n]; n %= MOD;
  int w = power(base[k + 2], MOD - 2), ans = 0;
  p[0] = q[k + 3] = 1;
  for (int i = 1; i <= k + 2; ++ i) p[i] = p[i - 1] * (n - i) % MOD;
  for (int i = k + 2; i; -- i) q[i] = q[i + 1] * (n - i) % MOD;
  for (int i = 1; i <= k + 2; ++ i) (ans += a[i] * w % MOD * p[i - 1] % MOD * q[i + 1]) %= MOD, w = w * (i - k - 2) % MOD * inv[i] % MOD;
  return (ans + MOD) % MOD;
}

signed main() {
  int T; read(T), base[1] = 1;
  for (int i = 1; i < K; ++ i) inv[i] = power(i, MOD - 2);
  for (int i = 2; i < K; ++ i) base[i] = base[i - 1] * (MOD + 1 - i) % MOD;
  while (T --) {
    read(n), read(k);
    for (int i = 1; i < k + 3; ++ i) a[i] = (a[i - 1] + power(i, k)) % MOD;
    printf("%lld\n", calc(n));
  }
  return 0;
}

算法分析2

此题也可以用伯努利数解决,因为
$$\sum_{i=1}^n i^k={1 \over k+1} \sum_{i=0}^k (-1)^i {k+1 \choose i} B_in^{k+1-i}$$
其中伯努利数由其指数型生成函数${x \over e^x-1}$定义。易知
$$\sum_{i=0}^{\infty} B_i{x^i \over i!}={x \over e^x-1}={x \over \sum_{i=1}^{\infty} {x^i \over i!}}={1 \over \sum_{i=0}^{\infty} {x^i \over (i+1)!}}$$
只要对分母求多项式逆元,即可得到伯努利数,时间复杂度$O(k\log k)$。其它部分均可$O(k)$预处理,答案也可以$O(k)$计算。因此总时间复杂度是$O(k\log k+Tk)$。

代码2

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

#define int long long

static int const N = 200000;
static int const MOD = 1000000007;
static int const M = 31622;
static double const PI = acos(-1);
int b[N], rev[N], fac[N], inv[N];
class complex {
private:
  double x, y;

public:
  complex(double _x = 0, double _y = 0) : x(_x), y(_y) {}
  double real() { return x; }
  friend complex operator+(complex const &a, complex const &b) {
    return complex(a.x + b.x, a.y + b.y);
  }
  friend complex operator-(complex const &a, complex const &b) {
    return complex(a.x - b.x, a.y - b.y);
  }
  friend complex operator*(complex const &a, complex const &b) {
    return complex(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
  }
} wn[N], A[N], B[N], C[N], D[N], E[N], F[N], G[N];

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

int init(int m) {
  int n = 1, l = 0;
  for (; n <= m; n <<= 1, ++l)
    ;
  for (int i = 1; i < n; ++i)
    rev[i] = rev[i >> 1] >> 1 | (i & 1) << l - 1;
  for (int i = 0; i < n >> 1; ++i)
    wn[i] = complex(cos(2 * PI / n * i), sin(2 * PI / n * i));
  return n;
}

void fft(complex *a, int n, bool inv = 0) {
  for (int i = 0; i < n; ++i)
    if (i < rev[i])
      std::swap(a[i], a[rev[i]]);
  for (int i = 1; i < n; i <<= 1)
    for (int j = 0; j < n; j += i << 1)
      for (int k = 0; k < i; ++k) {
        complex x = a[j + k], y = wn[n / (i << 1) * k] * a[j + k + i];
        a[j + k] = x + y, a[j + k + i] = x - y;
      }
  if (inv) {
    std::reverse(a + 1, a + n);
    for (int i = 0; i < n; ++i)
      a[i] = a[i].real() / n;
  }
}

int get_mod(double t) {
  return (int)(fmod(t, MOD) + MOD + 0.5) % MOD;
}

void get_inv(int *f, int *g, int n) {
  if (n == 1)
    return void(g[0] = power(f[0], MOD - 2));
  get_inv(f, g, n + 1 >> 1);
  int len = init(n << 1);
  for (int i = 0; i < n + 1 >> 1; ++i)
    A[i] = g[i] / M, B[i] = g[i] % M;
  for (int i = n + 1 >> 1; i < len; ++i)
    A[i] = B[i] = 0;
  for (int i = 0; i < n; ++i)
    C[i] = f[i] / M, D[i] = f[i] % M;
  for (int i = n; i < len; ++i)
    C[i] = D[i] = 0;
  fft(A, len), fft(B, len), fft(C, len), fft(D, len);
  for (int i = 0; i < len; ++i) {
    E[i] = 0 - A[i] * C[i];
    F[i] = 0 - A[i] * D[i] - B[i] * C[i];
    G[i] = 2 - B[i] * D[i];
  }
  fft(E, len, 1), fft(F, len, 1), fft(G, len, 1);
  for (int i = 0; i < n; ++i) {
    int x = get_mod(E[i].real()) * M % MOD * M % MOD;
    int y = get_mod(F[i].real()) * M % MOD;
    int z = get_mod(G[i].real());
    int w = (x + y + z) % MOD;
    C[i] = w / M, D[i] = w % M;
  }
  for (int i = n; i < len; ++i)
    C[i] = D[i] = 0;
  fft(C, len), fft(D, len);
  for (int i = 0; i < len; ++i) {
    E[i] = A[i] * C[i];
    F[i] = A[i] * D[i] + B[i] * C[i];
    G[i] = B[i] * D[i];
  }
  fft(E, len, 1), fft(F, len, 1), fft(G, len, 1);
  for (int i = 0; i < n; ++i) {
    int x = get_mod(E[i].real()) * M % MOD * M % MOD;
    int y = get_mod(F[i].real()) * M % MOD;
    int z = get_mod(G[i].real());
    g[i] = (x + y + z) % MOD;
  }
}

int get_c(int n, int m) {
  return fac[n] * inv[m] % MOD * inv[n - m] % MOD;
}

signed main() {
  int T;
  fac[0] = 1;
  for (int i = 1; i < N; ++i)
    fac[i] = fac[i - 1] * i % MOD;
  inv[N - 1] = power(fac[N - 1], MOD - 2);
  for (int i = N - 1; i; --i)
    inv[i - 1] = inv[i] * i % MOD;
  get_inv(inv + 1, b, 50001);
  for (int i = 0; i < 50001; ++i)
    (b[i] *= fac[i]) %= MOD;
  for (scanf("%lld", &T); T--;) {
    int n, k, ans = 0;
    scanf("%lld%lld", &n, &k), n %= MOD;
    for (int i = k, f = k & 1 ? -1 : 1, p = n; ~i; --i, f = -f, (p *= n) %= MOD)
      ans += (MOD + f) * get_c(k + 1, i) % MOD * b[i] % MOD * p % MOD;
    printf("%lld\n", ans % MOD * power(k + 1, MOD - 2) % MOD);
  }
  return 0;
}

Funny Strings

题目描述

Let’s consider a string of non-negative integers, containing $N$ elements. Suppose these elements are $S_1, S_2, \ldots, S_N$, in the order in which they are placed inside the string. Such a string is called ‘funny’ if the string $S_1+1, S_2, S_3, \ldots, S_{N-1}, S_N-1$ can be obtained by rotating the first string (to the left or to the right) several times. For instance, the strings $2, 2, 2, 3$ and $1, 2, 1, 2, 2$ are funny, but the string $1, 2, 1, 2$ is not. Your task is to find a funny string having $N$ elements, for which the sum of its elements $S_1+S_2+ \cdots +S_N$ is equal to $K$.

题意概述

定义序列的旋转操作为将序列的最后一个元素移到最前面,定义两个序列等价当且仅当可以通过若干次旋转操作使它们相同,定义一个序列是funny的当且仅当将它的第一个元素加一、最后一个元素减一后得到的序列和原序列等价。要求构造一个长度为$N$、元素之和为$K$的funny序列(所有元素均为非负整数)。
数据范围:$2 \le N \le 1000, \; 1 \le K \le 30000, \; (N, K)=1$。

算法分析

我们只考虑$1 \le K \le N$的情况,因为其他情况都可以通过把所有数减去同一个数得到这种情况。
显然,第一个数一定比最后一个数小$1$,否则新序列和原序列中某些数字出现的次数不同。假设我们有新旧序列如下:
0_______1(旧)
1_______0(新)
新旧序列中空位上的数字是一样的。这意味着我们只要知道了旋转次数,就可以构造出序列。假设旋转次数是$a$,那么第$i$位的数就旋转到了第$((i+a-1)\%N+1)$位。下面模拟$N=9, a=7$的构造过程:
第$8$位
0______11
1______10
第$6$位
0____1_11
1____1_10
第$4$位
0__1_1_11
1__1_1_10
第$2$位
01_1_1_11
11_1_1_10
第$9$位,构造完成
010101011
110101010
由于元素之和为$K$,因此序列中有$K$个$1$,也就是说,从第$1$位开始,模拟$K$次,到达第$N$位。那么$N-1 \equiv K \times a \pmod N$,$a \equiv (N-1) \times K^{-1} \pmod N$。因为$(N, K)=1$,所以$a$一定存在,接下来只要模拟即可。当然也可以用暴力求出$a$。

代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct IOManager {
  template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); }
  inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; }
  inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); }
  template <typename T> inline IOManager operator > (T &x) { read(x); return *this; }
  template <typename T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
  inline void write(char c) { putchar(c); }
  inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); }
  template <typename T> inline IOManager operator < (T x) { write(x); return *this; }
} io;

struct Solver {
private:
  static const int N = 1010;
  int n, k, a[N];
  void input() { io > n > k; }
  void init() {
    int t = k / n;
    for (int i = 1; i <= n; ++ i) a[i] = t, k -= t;
  }
  void process() {
    int sum = n - 1;
    while (sum % k) sum += n;
    int p = sum / k + 1;
    for (; p < n; p = (p - 1 + sum / k) % n + 1) ++ a[p]; ++ a[n];
    for (int i = 1; i <= n; ++ i) io < a[i] < ' ';
    io < '\n';
  }

public:
  void solve() { input(), init(), process(); }
} solver;

int main() {
  solver.solve();
  return 0;
}

Visit of the Great

题目描述

The Great Mushroom King descended to the dwarves, but not everyone managed to see him. Only the few chosen ones could see the King.
We know that only $LCM(k^{2^l}+1, k^{2^{l+1}}+1, \ldots, k^{2^r}+1)$ dwarves can see the Great Mushroom King. Numbers $k, l, r$ are chosen by the Great Mushroom King himself in some complicated manner which is unclear to common dwarves.
The dwarven historians decided to document all visits of the Great Mushroom King. For each visit the dwarven historians know three integers $k_i, l_i, r_i$, chosen by the Great Mushroom King for this visit. They also know a prime number $p_i$. Help them to count the remainder of dividing the number of dwarves who can see the King, by number $p_i$, for each visit.

题意概述

给定$t$组$k, l, r, p$,对于每一组求出$LCM(k^{2^l}+1, k^{2^{l+1}}+1, \ldots, k^{2^r}+1) \bmod p$。保证$p$是质数。
数据范围:$1 \le t \le 10^5, \; 1 \le k \le 10^6, \; 0 \le l \le r \le 10^{18}, \; 2 \le p \le 10^9$。

算法分析

可以证明$(k^{2^l}+1, k^{2^{l+1}}+1, \ldots, k^{2^r}+1) \le 2$。证明如下:

令$g=(k^{2^l}+1, k^{2^{l+1}}+1, \ldots, k^{2^r}+1)$
$g \mid k^{2^n}+1 \Leftrightarrow k^{2^n} \equiv -1 \pmod g$
两边同时平方可得$k^{2^{n+1}} \equiv 1 \pmod g \Leftrightarrow g \mid k^{2^{n+1}}-1$
$\because g \mid k^{2^{n+1}}+1$
$\therefore g \le 2$

由此得证。
令$s=\prod_{i=l}^r (k^{2^i}+1)={k^{2^{l+1}}-1 \over k^{2^l}-1} \cdot {k^{2^{l+2}}-1 \over k^{2^{l+1}}-1} \cdots {k^{2^{r+1}}-1 \over k^{2^r}-1}={k^{2^{r+1}}-1 \over k^{2^l}-1}$。根据费马小定理,$x^{p-1} \equiv 1 \pmod p$,可以在$O(\log r)$的时间内求出$s$。如果$k$是奇数,那么答案是${s \over 2^{r-l}} \bmod p$,否则答案就是$s \bmod p$。
还要考虑到两种特殊情况。一种是$p=2$,直接特判即可;另一种是$p \mid k^{2^l}-1$,这就意味着$\forall i \ge l, \; p \mid k^{2^i}-1$,这等价于$\forall i \ge l, \; k^{2^i}+1 \equiv 2 \pmod p$,因此答案是$2^{r-l+1} \bmod p$。

代码

import std.stdio;

long power(long a, long b, long mod) {
  if (b && ! (a % mod)) return 0;
  long ret = 1;
  while (b) {
    if (b & 1) (ret *= a) %= mod;
    (a *= a) %= mod, b >>= 1;
  }
  return ret;
}

long inv(long a, long p) {
  return power(a, p - 2, p);
}

int main() {
  int T; readf(" %d", &T);
  while (T--) {
    long k, l, r, p, q, ans;
    readf(" %d %d %d %d", &k, &l, &r, &p), q = p - 1;
    if (p == 2) {
      if (k & 1) writeln(0); else writeln(1);
      continue;
    }
    ans = (power(k, power(2, l, q) + q, p) + q) % p;
    if (! ans) ans = power(2, r - l + 1, p);
    else ans = (power(k, power(2, r + 1, q) + q, p) + q) * inv(ans, p) % p;
    if (k & 1) (ans *= power((p >> 1) + 1, r - l, p)) %= p;
    writeln(ans);
  }
  return 0;
}

Notes on Module

逆元

对于模意义下的除法,$a/x \equiv b \pmod m \Leftrightarrow a \times x^{-1} \equiv b \pmod m$,则称$x^{-1}$为$x$在模$m$意义下的逆元。
关于逆元的求法可以参考Notes on Multiplicative Inverse
考虑线性同余方程$ax \equiv b \pmod m$,有
$$(a/(a, m))x \equiv b/(a, m) \pmod {m/(a, m)}$$
显然,当$(a, m) \not \mid b$时,原方程无解;否则,有
$$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))$$
原方程可能有多解,也可能无解。


费马小定理

当$p$是素数时,对任意整数$x$都有$x^p \equiv x \pmod p$。若$p \not \mid x$,则
$$
\begin{align}
x^{p-1} &\equiv 1 \pmod p \\
x^{-1} &\equiv x^{p-2} \pmod p
\end{align}
$$
当$m$不是素数且$x$与$m$互质时,有
$$x^{\varphi(m)} \equiv 1 \pmod m$$
其中$\varphi(m)$为欧拉函数,其值等于不大于$m$的正整数中与$m$互质的数的个数。
利用线性筛,每次发现质数$p$时把它倍数的欧拉函数乘上$(p-1)/p$,就可以求出$1$到$n$的欧拉函数。


线性同余方程组

给定由若干个形如$a_ix \equiv b_i \pmod {m_i}$的方程组成的方程组,求它的解。如果有解,则一定有无穷多解,并可以表示为$x \equiv b \pmod m$的形式,因此问题转化为求解$b$和$m$。如果我们能求解方程组
$$
\left\{
\begin{align}
x &\equiv b_i \pmod {m_i} \\
ax &\equiv b_{i+1} \pmod {m_{i+1}}
\end{align}
\right.
$$
那么只要对方程逐个求解即可得到答案。
因为$x \equiv b_i \pmod {m_i}$,所以$x=tm_i+b_i$,代入第二个式子,得到
$$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}}$$
这是一个一次同余方程。当$(am_i, m_{i+1}) \not \mid b_{i+1}-ab_i$时原方程组无解。


中国剩余定理

如果同余方程组满足
$$\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}$$
反之,对于一个合数$n$,如果$n=ab \land (a, b)=1$,那么$x \bmod n$的值确定了之后,$x \bmod a$和$x \bmod b$的值也就确定了。因此,以$n$为模数来考虑和以$a$、$b$为模数来考虑是等价的。这个定理叫做中国剩余定理。
所以,对于模合数的情况只要考虑模若干$p^k$($p$为素数)的情况就可以了。如果$n$是一个square-free的数,那么问题就转化成模素数的情况,从而变得容易求解。
若$n$不是square-free的数,可以将每个数字$x$用一个二元组$(a, b)$表示,代表$x=ap_i^b$。有以下运算规则
$$
\begin{align}
(a, b)\times(c, d)&=(ac, b+d) \\
(a, b)/(c, d)&=(ac^{-1}, b-d)
\end{align}
$$
关于扩展中国剩余定理可参考Strange Way to Express Integers


$n!$

在计数问题中经常用到$n!$。因此有必要了解$n!$在模$p$意义下的一些性质。
假设$p$是素数,$n!=ap^e \; (a \not \mid p)$,求$a \bmod p$和$e$,$e$是$n!$能够迭代整除$p$的次数。显然$$e=n/p+n/p^2+n/p^3+ \cdots$$
因为$n/d$等于不超过$n$的能被$d$整除的正整数个数。
接下来计算$a \bmod p$。可以发现,不能被$p$整除的项在模$p$意义下呈周期性,它们的积为
$$((p-1)!)^{n/p} \times (n \bmod p)!$$
事实上,根据威尔逊定理,$(p-1)! \equiv -1 \pmod p$。因为除了$1$和$p-1$之外的其余项都可以和各自的逆元相乘得到$1$。
接下来计算可以被$p$整除的项的积。可以被$p$整除的项为$p, 2p, 3p, \ldots, (n/p)p$,将$p$消去后得到$1, 2, 3, \ldots, n/p$。因此问题的范围就由$n$缩小到了$n/p$。


${n \choose k} \bmod p$

当$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 \choose k}={n! \over k!(n-k)!}$$

$$n!=a_1p^{e_1}, \; k!=a_2p^{e_2}, \; (n-k)!=a_3p^{e_3}$$
从中可以看出,当$e_1 \gt e_2+e_3$时,${n \choose k}$可以被$p$整除;当$e_1=e_2+e_3$时,${n \choose k}$无法被$p$整除,此时${n \choose k} \equiv a_1(a_2a_3)^{-1} \pmod p$。
关于扩展卢卡斯定理可参考Ceizenpok’s Formula

Digit Tree

题目描述

ZS the Coder has a large tree. It can be represented as an undirected connected graph of $n$ vertices numbered from $0$ to $n-1$ and $n-1$ edges between them. There is a single nonzero digit written on each edge.
One day, ZS the Coder was bored and decided to investigate some properties of the tree. He chose a positive integer $M$, which is coprime to $10$, i.e. $(M, 10)=1$.
ZS consider an ordered pair of distinct vertices $(u, v)$ interesting when if he would follow the shortest path from vertex $u$ to vertex $v$ and write down all the digits he encounters on his path in the same order, he will get a decimal representaion of an integer divisible by $M$.
Formally, ZS consider an ordered pair of distinct vertices $(u, v)$ interesting if the following states true:

  • let $a_1=u, a_2, \ldots, a_k=v$ be the sequence of vertices on the shortest path from $u$ to $v$ in the order of encountering them;
  • let $d_i (1 \le i \lt k)$ be the digit written on the edge between vertices $a_i$ and $a_i+1$;
  • the integer $\overline{d_1d_2 \ldots d_{k-1}}=\sum_{i=1}^{k-1} 10^{k-1-i}d_i$ is divisible by $M$.

Help ZS the Coder find the number of interesting pairs!

题意概述

给定一棵有$n$个节点的树和一个与$10$互质的数$M$,树上每条边的权值都是小于$10$的正整数。定义$dist_{u, v}$为依次写下从$u$到$v$路径上每条边的权值所得到的数字。求满足$M \mid dist_{u, v}$的点对个数。
数据范围:$2 \le n \le 10^5, \; 1 \le M \le 10^9$。

算法分析

设当前枚举到的节点为$x$。令$depth_u$表示$u$在$x$及它子树中的深度。对于在$x$第$(i+1)$棵子树中的节点$u$和在前$i$棵子树中的节点$v$,有:
$$
\begin{align}
M \mid dist_{u, v} \Leftrightarrow 10^{depth_v}dist_{u, x}+dist_{x, v} \equiv 0 \pmod M \tag{1} \\
M \mid dist_{v, u} \Leftrightarrow 10^{depth_u}dist_{v, x}+dist_{x, u} \equiv 0 \pmod M \tag{2}
\end{align}
$$
对于$(1)$式,化简得$dist_{u, x} \equiv -10^{-depth_v}dist_{x, v} \pmod M$;对于$(2)$式,化简得$10^{-depth_u}dist_{x, u} \equiv -dist_{v, x} \pmod M$。用两个map分别存下前$i$棵子树中$10^{-depth_v}dist_{x, v}$和$dist_{v, x}$的值,在处理第$(i+1)$棵子树时直接加上可行的方案数。

代码

#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;
struct edge {
    int v, w, nxt;
} e[200001];
long long n, m, ans, nume, tot, root, h[100001], size[100001], f[100001];
long long val1[100001], val2[100001], power[100001], inv[100001];
bool vis[100001];
map<long long, int> id1, id2;
void extend_gcd(int a, int b, int &x, int &y) {
    if (!b) { x = 1, y = 0; return; }
    extend_gcd(b, a % b, y, x);
    y -= a / b * x;
}
void add_edge(int u, int v, int w) {
    e[++nume].v = v, e[nume].w = w, e[nume].nxt = h[u], h[u] = nume;
    e[++nume].v = u, e[nume].w = w, e[nume].nxt = h[v], h[v] = nume;
}
void get_root(int t, int fa) {
    size[t] = 1, f[t] = 0;
    for (int i = h[t]; i; i = e[i].nxt) {
        if (!vis[e[i].v] && e[i].v != fa) {
            get_root(e[i].v, t);
            size[t] += size[e[i].v];
            f[t] = max(f[t], size[e[i].v]);
        }
    }
    f[t] = max(f[t], tot - size[t]);
    if (f[t] < f[root]) root = t;
}
void get_dist(int t, int fa, int flag, int depth) {
    if (!flag) ++id1[val1[t]], ++id2[val2[t] * inv[depth] % m];
    else {
        ans += !val1[t] + !val2[t];
        ans += id1[(val2[t] ? m - val2[t] : 0) * inv[depth] % m];
        ans += id2[val1[t] ? m - val1[t] : 0];
    }
    for (int i = h[t]; i; i = e[i].nxt) {
        if (!vis[e[i].v] && e[i].v != fa) {
            if (flag) {
                val1[e[i].v] = (val1[t] + e[i].w * power[depth]) % m;
                val2[e[i].v] = (val2[t] * 10 + e[i].w) % m;
            }
            get_dist(e[i].v, t, flag, depth + 1);
        }
    }
}
void solve(int t) {
    vis[t] = true, id1.clear(), id2.clear();
    for (int i = h[t]; i; i = e[i].nxt) {
        if (!vis[e[i].v]) {
            val1[e[i].v] = val2[e[i].v] = e[i].w % m;
            get_dist(e[i].v, t, 1, 1);
            get_dist(e[i].v, t, 0, 1);
        }
    }
    for (int i = h[t]; i; i = e[i].nxt) {
        if (!vis[e[i].v]) {
            root = n, tot = size[e[i].v];
            get_root(e[i].v, t);
            solve(root);
        }
    }
}
int main()
{
    scanf("%lld%lld", &n, &m);
    power[0] = 1;
    for (int i = 1; i <= n; ++i) power[i] = power[i - 1] * 10 % m;
    for (int i = 0; i <= n; ++i) {
        int x, y;
        extend_gcd(power[i], m, x, y);
        inv[i] = (x % m + m) % m;
    }
    for (int i = 1; i < n; ++i) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add_edge(u, v, w);
    }
    tot = f[n] = n, root = n;
    get_root(0, n);
    solve(root);
    printf("%lld\n", ans);
    return 0;
}

Notes on Multiplicative Inverse

扩展欧几里得算法求$a$对模$b$的逆

当$(a, b)=1$时,有
$$\exists x, y \in Z, \; ax+by=1$$
扩展欧几里得算法证明如下:

设$a \gt b$。
当$b=0$时,有
$$a \times 1+b \times 0=a=(a, b)=1$$
此时$x=1, \; y=0$。
当$b \neq 0$时,有
$$
\left\{
\begin{align}
a \times x_1+b \times y_1&=1 \\
b \times x_2+a \bmod b \times y_2&=1
\end{align}
\right.
$$
所以
$$a \times x_1+b \times y_1=b \times x_2+a \bmod b \times y_2$$
将$a \bmod b=a-a/b \times b$代入,得
$$a \times x_1+b \times y_1=b \times x_2+a \times y_2-a/b \times b \times y_2$$
那么$x_1=y_2, \; y_1=x_2-a/b \times y_2$。

由此得证。

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


费马小定理求$a$对模$p$的逆

当$p$是质数且$p \nmid x$时,有
$$x^{-1} \equiv x^{p-2} \pmod p$$
证明如下:

根据费马小定理,当$p$是质数时,有
$$\forall x \in Z, \; x^p \equiv x \pmod p$$
当$p \nmid x$时,有
$$
\begin{align}
x^{p-1} &\equiv 1 \pmod p \\
x^{-1} &\equiv x^{p-2} \pmod p
\end{align}
$$

由此得证。


$O(n)$时间求出$1..n$对模$p$的逆

当$p$是质数且$1 \lt i \lt p$时,有
$$i^{-1} \equiv (p-p/i) \times (p \bmod i)^{-1} \pmod p$$
证明如下:

令$t=p/i, \; k=p \bmod i$。易知
$$
\begin{align}
t \times i+k &\equiv 0 \pmod p \\
k &\equiv -t \times i \pmod p
\end{align}
$$
等式两边同时除以$ik$,得
$$
\begin{align}
i^{-1} &\equiv -t \times k^{-1} \pmod p \\
i^{-1} &\equiv -p/i \times (p \bmod i)^{-1} \pmod p
\end{align}
$$

$$i^{-1} \equiv (p-p/i) \times (p \bmod i)^{-1} \pmod p$$

由此得证。

void get_inv() {
    inv[1] = 1;
    for (int i = 2; i < MOD; ++i) {
        inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
    }
}


求$b \mid a$时${a \over b}$在模$n$意义下的值

当$b \mid a$时,有
$${a \over b} \bmod n=a \bmod (bn) / b$$
证明如下:


$${a \over b} \bmod n = x$$
则有
$$
\begin{align}
{a \over b}&=kn+x \\
a&=kbn+bx
\end{align}
$$
因为$0 \le x \lt n$,所以
$$
\begin{align}
a \bmod (bn)&=bx \\
x&=a \bmod (bn) / b
\end{align}
$$

由此得证。