数论

CRT用于求解类似$$\left\{\begin{aligned}&x \equiv a_1 \pmod{m_1} \\&x \equiv a_2 \pmod{m_2} \\&… \\&x \equiv a_n \pmod{m_n}\end{aligned}\right.$$其中，$\forall i, j, ~ (m_i, m_j) = 1$ 设 $M = \prod_{i = 1}^n m_i, ~ M_i = \frac{M}{m_i}$，再设 $M_it_i \equiv 1 \pmod{m_i}$，其中 $1 \le i \le n$ 则可构造一解 $x = \sum\limits_{i = 1}^n a_iM_it_i$，任意解 $x_0 = x + k \times M$ ExCRT用于求解类似$$\left\{\begin{aligned}&x \equiv a_1 \pmod{m_1} \\&x \equiv a_2 \pmod{m_2} \\&… \\&x \equiv a_n \pmod{m_n}\e ...

根据Crash的数字表格，很容易可以将式子化简为$$\begin{aligned} Ans &= \sum\limits_{i = 1}^n \sum\limits_{j = 1} ij(i, j) \\ &= \sum\limits_{d = 1}^n d^3 \sum\limits_{k = 1}^{\left\lfloor\frac{n}{d}\right\rfloor} \mu(k) k^2 \left( \sum\limits_{i = 1}^{\left\lfloor\frac{n}{kd}\right\rfloor} i \right)^2 \end{aligned}$$感觉 $d, k$ 放在一起式子无法继续化简，主要是有 $kd$ 存在，故令 $T = kd$ ，则有$$Ans = \sum\limits_{T = 1}^n \left( \sum\limits_{i = 1}^{\left\lfloor\frac{n}{T}\right\rfloor} i \right)^2 T^2 \sum\limits_{d | T} d \mu(\frac{T ...

前置知识多项式除法|取模该部分见 多项式操作 特征值与特征向量（这部分我也不怎么理解，就大概记个结论） 对 $n$ 阶矩阵 $A$ 的特征向量 $\vec{v}$ 与，有特征值 $\lambda$ 满足$$A\vec v = \lambda\vec v$$移项则有 $(\lambda I - A)\vec v = 0$，其中 $I$ 为单位矩阵 那么有解的充要条件是 $det(\lambda I - A) = 0$ 令 $f(\lambda) = det(\lambda I - A)$，即此时可将 $det (\lambda I - A)$ 看作一个 $n$ 阶多项式，则称 $f(\lambda)$ 为矩阵 $A$ 的特征多项式，对矩阵 $A$，其任意特征值 $\lambda_0$ 都满足 $f(\lambda_0) = 0$ $\text{Hamiton-Cayley}$定理对矩阵 $A$ 及其特征多项式 $f(x)$，满足 $f(A) = O$，其中 $O$ 为零矩阵 证明留坑 常系数齐次线性递推求一个满足 $k$ 阶齐次线性递推数列 $h_i$ 的第 $n$ 项，即$$h_n = ...

多项式求逆该部分见 多项式求逆 多项式除法|取模有 $F(x) = G(x)Q(x) + R(x)$，给定 $F(x)$ 与 $G(x)$，求解 $Q(x), R(x)$，其中 $F(x), G(x)$ 最高次数分别为 $n, m$ 显然地，$Q(x), R(x)$ 的最高次数必定不超过 $n - m, m - 1$，考虑式子变形$$\begin{aligned}&F(x) = G(x)Q(x) + R(x) \\\Rightarrow &F(\frac1x) = G(\frac1x)Q(\frac1x) + R(\frac1x) \\\Rightarrow &x^nF(\frac1x) = x^mG(\frac1x)x^{n - m}Q(\frac1x) + x^{n - m + 1}x^{m - 1}R(\frac1x) \\\end{aligned}$$令 $A_R(x)$ 表示 $A(x)$ 系数翻转后得到的多项式，即 $A(x)$ 系数 $(a_0, a_1, …, a_n)$，$A_R(x)$ 系数 $(a_n, a_{n - 1}, …, a_1) ...

题意将题意转化一下 有 $m = \sum\limits_{i = 1}^n w_i$ 个数，前 $n$ 个中第 $i$ 个为 $w_i − 1$ ，剩下的 $m − n$ 个数都是 $− 1$ 求对这 $m$ 个数 $m!$ 种重排的方案中，有多少种满足重排后的序列任意前缀和不为负 题解卡特兰数的另一种组合意义首先有一个引理 给定 $n$ 个 $1$ 和 $n$ 个 $- 1$，它们组成一个长度为 $2n$ 的序列 $a$，则必定存在一个 $i$ 使得序列 $a_{i + 1…2n} + a_{1…i}$ 满足任意前缀都不小于零 证明也很简单，找到一个使得前缀和最小的位置 $i$，设 $s_{i,j}$ 表示 $a$ 上 $a_i$ 到 $a_j$ 的和，那么显然 $s_{i + 1, 2n} \ge 0$，对 $\forall k \in [1, i]$，$s_{i + 1, 2n} + s_{1, k} \ge 0$ 那么接下来求解 $n$ 个 $1$ 和 $n$ 个 $- 1$ 组成的合法序列（即任意前缀和不小于零）的方案数，也就是卡特兰数 $1$ 的编号为 $1 \sim ...

题意求 $\sum\limits_{i = 1}^N \sum\limits_{j = 1}^M lcm (i, j)$ Solution易知，原式$$\sum\limits_{i = 1}^N \sum\limits_{j = 1}^M \frac{ij}{\gcd (i, j)}$$枚举 $\gcd (i, j)$ ，且将 $d$ 提出来得$$\sum\limits_{d = 1}^{\min (N, M)} d \sum\limits_{i = 1}^{\left\lfloor\frac{N}{d}\right\rfloor} \sum\limits_{j = 1}^{\left\lfloor\frac{M}{d}\right\rfloor} ij[(i, j) = 1]$$将公式 $\sum\limits_{k | n} \mu(k) = [n = 1]$ 代入，得$$\sum\limits_{d = 1}^{\min (N, M)} d \sum\limits_{i = 1}^{\left\lfloor\frac{N}{d}\right\rfloor} \sum\limits ...

题意给定 $n$ 行 $m$ 列的 $01$ 矩阵，求满足 $\big(\sum_{\forall i \in A, j \in B} value_{i, j}\big) \equiv 0 \pmod{2}$ 的二元组的数量 题解首先考虑 $n = 1$，令 $1$ 的个数为 $t$，可以发现答案$$\sum\limits_{k = 0}^{\lfloor\frac{m}{2}\rfloor} \dbinom{t}{2k} \times 2^{m - t} - 1 = 2^{m - 1} - 1$$至于证明，可以考虑已经选好的数列 $\{a_1, a_2, …, a_n\}$，那么现在考虑加入第 $n +1$ 个，显然加入 $0, 1$ 都是多了两种选择 那么现在考虑将行合并成一列 但是问题是如果需要枚举选的行还是需要 $2^n$ 的复杂度，然后我考场上就想到这就凉了 那么显然每次选好了行，再选列的时候这若干个列会贯穿所有行，那就可以将每行看作一个数，并且将它们合并（异或）起来，这样就变成做 $n = 1$ 的情况了 接下来只要考虑有几种情况会使得其异或和为 $1$ （或不为 $1$） ...

前置知识Matrix-Tree定理对于无向图 $G$，定义其度数矩阵 $D$$$\left[\begin{matrix}deg_1 & 0 & 0 & \cdots & 0 \\0 & deg_2 & 0 & \cdots & 0 \\0 & 0 & deg_3 & \cdots & 0 \\\vdots & \vdots & \vdots & \ddots & \vdots \\0 & 0 & 0 & 0 & deg_n\end{matrix}\right]$$定义其邻接矩阵 $C$$$\left[\begin{matrix}0 & a_{1,2} & a_{1,3} & \cdots & a_{1,n} \\a_{2,1} & 0 & a_{2,3} & \cdots & a_{2,n} \\\vdots & \vdots & \vdots &a ...

题意求解 $1 \le x \le n, ~ 1 \le y \le m$ 中满足在 $k$ 进制下 $\frac{x}{y}$ 是有限循环小数的个数 题解很好然后我一开始在计算器上敲了半个小时然后由于眼瞎并且归纳能力差并没有发现规律 设 $\frac{x}{y}$ 的循环节长度为 $l$，则有$$\begin{aligned}\frac{xk^l}{y} - \left\lfloor\frac{xk^l}{y}\right\rfloor &= \frac{x}{y} - \left\lfloor\frac{x}{y}\right\rfloor \\xk^l - \left\lfloor\frac{xk^l}{y}\right\rfloor y &= x - \left\lfloor\frac{x}{y}\right\rfloor y \\xk^l &\equiv x \pmod y \\k &\equiv 1 \pmod y\end{aligned}$$也就是说只要满足 $y \bot k$ 即可满足题意，故可将问题化为$$\begin{aligned ...

这题一直往 $\text{dp}$ 去想，然后就没了 所以其实并不用注意之前的可看见的建筑的最大值是多少，若把那些能够被看见的建筑之间构成的区间看作一个小组，那么能够被看见的建筑不过是在当前小组中选择一个最大值最为代表排在左（右）边罢了 所以现在问题转化为将 $n - 1$ 个建筑分在 $A + B - 2$ 个盒子，然后盒子内可以随意排列的个数 然后上述问题实际上可以将每个盒子看作一个圆，故问题又转化为 $n - 1$ 个建筑构成的 $A + B - 2$ 个圆排列方案数，即斯特林数 $S (n - 1, A + B - 2)$ 然后要在其中选择一些放左（右）边，故答案即为$$ans = S (n - 1, A + B - 2) \times \dbinom{A + B - 2}{A - 1}$$ 代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#include <iostream> ...