Q779’s Blog

威尔逊定理（Wilson 定理） 内容 对于素数 \(p\) 有 \[ (p-1) ! \equiv-1(\bmod p) \] 对于整数 \(n\) ，令 \((n!)_p\) 表示所有小于等于 \(n\) 但不能被 \(p\) 整除的正整数的乘积，即 \[ (n !)_p=n ! /\left(\lfloor n / p\rfloor ! p^{\lfloor n / p\rfloor}\right) \] 威尔逊定理指出 \((p !)_p=(p-1) ! \equiv-1 \pmod{p}\) 且可被推广至模素数 \(p\) 的幂次。 应用 1. 阶乘 & 素数 （这一段我本来想直接搬 oiwiki 的文本的，然而这 oiwiki 怕不是机翻的） 在某些情况下需要考虑以素数 \(p\) 为模数的公式，而且是含有分子和分母都含有阶乘的某些分式 考虑用 \(p\) 的幂次的形式表示 \((n!)_p\) ，如下 \[ \begin{aligned} (n !)_p= & 1 \times 2 \times 3 \times \cdots \times(p-2...

洛谷P3232 [HNOI2013] 游走 题解 题目链接：P3232 [HNOI2013] 游走 题意： 给定一个 \(n\) 个点 \(m\) 条边的无向连通图，顶点从 \(1\) 编号到 \(n\)，边从 \(1\) 编号到 \(m\)。 小 Z 在该图上进行随机游走，初始时小 Z 在 \(1\) 号顶点，每一步小 Z 以相等的概率随机选择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小 Z 到达 \(n\) 号顶点时游走结束，总分为所有获得的分数之和。 现在，请你对这 \(m\) 条边进行编号，使得小 Z 获得的总分的期望值最小。 输入格式： 第一行是两个整数，分别表示该图的顶点数 \(n\) 和边数 \(m\)。 接下来 \(m\) 行每行两个整数 \(u,v\)，表示顶点 \(u\) 与顶点 \(v\) 之间存在一条边。 输出格式： 输出一行一个实数表示答案，保留三位小数。 数据范围： 保证 \(2\leq n \leq 500\)， \(1 \leq m \leq 125000\)，\(1 \leq u, v \leq n\) 给出的图...

洛谷P10143 [WC2024] 代码堵塞 题解 题目链接：P10143 [WC2024] 代码堵塞 题意： 小 \(\beth\) 为了纪念停办的 codejam，准备了一场“代码堵塞纪念赛”。小 \(\beth\) 的朋友小 \(\mho\) 也来围观，于是小 \(\beth\) 想预测小 \(\mho\) 的成绩。 比赛共 \(T\) 秒，有 \(n\) 道题。第 \(i(1 \le i \le n)\) 题分数为 \(a_i\)，小 \(\beth\) 预测小 \(\mho\) 需要 \(t_i\) 秒完成。 题目有两种类型：结果可见和结果不可见。结果不可见的题在比赛结束后才能知道评测结果，而结果可见的题在提交后立即得到评测结果。小 \(\beth\) 还没确定每道题的类型。 小 \(\mho\) 由于从不写对拍，所以会先按编号从小到大完成所有结果可见的题，再按编号从小到大完成所有结果不可见的题。小 \(\mho\) 会花 \(t_i\) 秒完成第 \(i\) 题，当小 \(\mho\) 花费在第 \(i\) 题和在第 \(i\) 题之前完成的所有题的时间总和不超过 ...

升幂引理 发现自己居然没有写过升幂引理的东西。 因为证明比较简单，所以本文就不写了，想知道就看参考文献[1]吧。 以下设 \(p\) 为质数，令 \(x,y\) 为满足 \(p \not\mid x\) 且 \(p \not\mid y\) 的整数，且 \(n\) 为正整数 升幂（Lift the Exponent，LTE）引理是初等数论中比较常用的一个定理。 定义 \(v_p(n)\) 为整数 \(n\) 标准分解中素因数 \(p\) 的幂次，即 \(n = \prod_{p \mid n} p^{v_p(n)}\) 。 第一部分 对于所有的素数 \(p\) 和满足 \(\gcd(n, p) = 1\) 的整数 \(n\) ： 若 \(p \mid x - y\)​ ，则 \[ v_p\left(x^n-y^n\right)=v_p(x-y) \] 若 \(p \mid x + y\) ，则对奇数 \(n\)​ 有 \[ v_p\left(x^n+y^n\right)=v_p(x+y) \] 第二部分 对于奇素数 \(p\)​ 和任意正整数 \(n\) 若 \(p \m...

洛谷P4725 【模板】多项式对数函数（多项式 ln） 题解 题目链接：P4725 【模板】多项式对数函数（多项式 ln） 题意： 给出 \(n-1\) 次多项式 \(A(x)\)，求一个 \(\bmod{\:x^n}\) 下的多项式 \(B(x)\)，满足 \(B(x) \equiv \ln A(x)\) 。 在模 \(998244353\) 意义下进行，且 \(a_i \in [0, 998244353) \cap \mathbb{Z}\) 。保证 \(a_0 = 1\) 。 输入格式： 第一行一个整数 \(n\) 。 下一行有 \(n\) 个整数，依次表示多项式的系数 \(a_0, a_1, \cdots, a_{n-1}\) 。 输出格式： 输出 \(n\) 个整数，表示答案多项式中的系数 \(a_0, a_1, \cdots, a_{n-1}\) 。 数据范围： 对于 \(100\%\) 的数据，\(1\le n \le 10^5\) 。 给定整系数多项式 \(f(x)\) ，求 \(g(x)\) 满足 \[ g(x) \equiv \ln f(x) \pmod{x...

洛谷P4512 【模板】多项式除法 题解 题目链接：P4512 【模板】多项式除法 题意： 给定一个 \(n\) 次多项式 \(F(x)\) 和一个 \(m\) 次多项式 \(G(x)\) ，请求出多项式 \(Q(x)\), \(R(x)\)，满足以下条件： \(Q(x)\) 次数为 \(n-m\)，\(R(x)\) 次数小于 \(m\) \(F(x) = Q(x) G(x) + R(x)\) 所有的运算在模 \(998244353\) 意义下进行。 输入格式： 第一行两个整数 \(n\)，\(m\)，意义如上。 第二行 \(n+1\) 个整数，从低到高表示 \(F(x)\) 的各个系数。 第三行 \(m+1\) 个整数，从低到高表示 \(G(x)\)​​ 的各个系数。 输出格式： 第一行 \(n-m+1\) 个整数，从低到高表示 \(Q(x)\) 的各个系数。 第二行 \(m\) 个整数，从低到高表示 \(R(x)\) 的各个系数。 如果 \(R(x)\) 不足 \(m-1\) 次，多余的项系数补 \(0\)​​。 数据范围： 对于所有数据，\(1 \le m < ...

洛谷P5205 【模板】多项式开根 题解 题目链接：P5205 【模板】多项式开根 题意： 给定一个 \(n-1\) 次多项式 \(A(x)\)，求一个在 \({} \bmod x^n\) 意义下的多项式 \(B(x)\)，使得 \(B^2(x) \equiv A(x) \pmod{x^n}\)​。若有多解，请取零次项系数较小的作为答案。 多项式的系数在模 \(998244353\) 意义下进行运算，本题保证 \(a_0 = 1\)。 输入格式： 第一行一个正整数 \(n\)。 接下来 \(n\) 个整数，依次表示多项式的系数 \(a_0, a_1, \dots, a_{n-1}\)。 输出格式： 输出 \(n\) 个整数，表示答案多项式的系数 \(b_0, b_1, \dots, b_{n-1}\)。 数据范围： 对于 \(100 \%\) 的数据：\(1 \le n \leq 10^5\)，\(0 \le a_i < 998244353\)。 设答案为 \(g(x)\) 。因为 \([x^0]g(x)\) 不为 \(0\) ，易知 \[ [x^0]f(x) = \s...

洛谷P4238 【模板】多项式乘法逆 题解 题目链接：P4238 【模板】多项式乘法逆 题意： 给定一个多项式 \(F(x)\) ，请求出一个多项式 \(G(x)\)， 满足 \(F(x) \cdot G(x) \equiv 1 \pmod{x^n}\)。系数对 \(998244353\) 取模。 输入格式： 首先输入一个整数 \(n\)， 表示输入多项式的项数。 接着输入 \(n\) 个整数，第 \(i\) 个整数 \(a_i\) 代表 \(F(x)\) 次数为 \(i-1\) 的项的系数。 输出格式： 输出 \(n\) 个数字，第 \(i\) 个整数 \(b_i\) 代表 \(G(x)\) 次数为 \(i-1\) 的项的系数。保证有解。 数据范围： 对于 \(100\%\) 的数据，\(1 \leq n \leq 10^5\)，$ 0 a_i ^9$。 首先，易知 \[ [x^0]f^{-1}(x) = ([x^0]f(x))^{-1} \] 假设现在已经求出了 \(f(x)\) 在模 \(x^{\left\lceil\frac{n}{2}\right\rceil}\) ...

多项式初等函数 本文主要介绍多项式的初等函数的定义以及在 OI 中如何求解。 注意，多项式的初等函数一般定义在模 \(x^n\) 意义下，但是在 OI 中，多项式系数通常还需要另外模一下 \(p\)​ 。 友情提醒：多项式模板题里的 \(n\)​​​ 表示的含义可能有细微差异（表示次数/项数），请注意分辨。 另外，本文中的代码并没有完全清空数组（懒），因此注意多测的清空问题。 1. 多项式求逆 给定多项式 \(f(x)\) ，求 \(f^{-1}(x)\)​ ，满足 \[ f^{-1}(x)f(x)\equiv 1 \pmod{x^n} \] 解法： 首先，易知 \[ [x^0]f^{-1}(x) = ([x^0]f(x))^{-1} \] 假设现在已经求出了 \(f(x)\) 在模 \(x^{\left\lceil\frac{n}{2}\right\rceil}\) 下的逆元 \(f_0^{-1}(x)\) ，有 \[ \begin{aligned} f(x) f_0^{-1}(x) & \equiv 1 &\pmod{ x^{\left\lceil\fr...

洛谷P4921 [MtOI2018] 情侣？给我烧了！ 题解 题目链接：P4921 [MtOI2018] 情侣？给我烧了！ 题意： 有 \(n\) 对情侣来到电影院观看电影。在电影院，恰好留有 \(n\) 排座位，每排包含 \(2\) 个座位，共 \(2×n\) 个座位。 现在，每个人将会随机坐在某一个位置上，且恰好将这 \(2 × n\) 个座位坐满。 如果一对情侣坐在了同一排的座位上，那么我们称这对情侣是和睦的。 你的任务是求出当 \(k = 0, 1, ... , n\) 时，共有多少种不同的就坐方案满足恰好有 \(k\) 对情侣是和睦的。 两种就坐方案不同当且仅当存在一个人在两种方案中坐在了不同的位置。不难发现，一共会有 \((2n)!\) 种不同的就坐方案。 由于结果可能较大，因此输出对 \(998244353\) 取模的结果。 输入格式： 输入包含多组数据。 输入的第 \(1\) 行包含 \(1\) 个正整数 \(T(1 \leq T \leq 1000)\)，表示数据的组数。 接下来 \(T\) 行，每行包含 \(1\) 个正整数 \(n(1 \leq n \le...

小蓝书 16.3 题解 传送门：小蓝书16.3 例题 例1 求解下列递推式的通项 \[ a_0=-1,~a_1=1 \\[6pt]a_n=2 a_{n-1}+3 a_{n-2}+3^n,~n>1 \] 解： 记 \(F(x)=\sum_{n=0}^{\infty} a_n x^n\) ，并定义 \(a_x=0(x<0)\) 。 考虑把原式写成一个方程 \[ a_n = 2a_{n-1} + 3a_{n-2} + 3^n - 2\times [n=0] \] 两边同时乘上 \(x^n\) 并求和 \[ \sum_{n \ge 0}a_nx^n = 2\sum_{n\ge 0}a_{n-1}x^n + 3\sum_{n\ge 0}a_{n-2}x^n + \sum_{n\ge 0}3^nx^n - 2 \] 即 \[ F(x) = 2xF(x) + 3x^2F(x) + \frac{6x-1}{1-3x} \] 解得 \[ (1-2 x-3 x^2)F(x) = \frac{6 x-1}{1-3 x} \] 因此 \[ F(x) =\frac{6 x-1}{(1+x)(...

洛谷P2012 拯救世界2 题解 题目链接：P2012 拯救世界2 题意： 经过 12 年的韬光养晦，世界末日再次来临（众人：什么鬼逻辑……）。 这次，小a 和 uim 已经做好了一切准备，顺利召唤出了 kkksc03 大神和 lzn 大神。然而，kkksc03 和 lzn 告诉他们，这次世界末日太过强大，他们已无法挽回，只有创世神 JOHNKRAM 能拯救这个世界。 然而，创世神 JOHNKRAM 是无法召唤的，除非把整个宇宙按照 \(E=mc^2\) 全部转化成能量。因为根据 C_SUNSHINE 大神随手推算出的召唤定律，至少需要被召唤者百万亿分之一的能量才能召唤（众人：什么鬼定律……）。 当然，还有一种方法，那就是找出创世神 JOHNKRAM 的基因序列。普通人基因序列由 A、C、G、T 构成，创世神 JOHNKRAM 不是普通人（是个胖纸），基因序列也不一样。除了这四种普通的，还有乾、兑、离、震、巽、坎、艮、坤八种特殊基因。其中乾、坎、艮、震属阳，只能出现奇数次；坤、兑、离、巽属阴，只能出现偶数次。 现在只知道创世神 JOHNKRAM 的基因序列共有 \(n\) 位，...