多项式求逆元

概述

多项式求逆元是多项式除法和多项式取模的必要过程，在竞赛中，有时候多项式求逆元的应用比多项式的除法还要多，用快速傅里叶变换以及倍增算法可以做到在 $\mathcal O(n\log n)$ 的时间内求出一个多项式的逆元

基本概念

在介绍多项式的逆元之前，先说明一些概念：多项式的度、多项式的逆元、多项式的除法和取余

对于一个多项式 $A(x)$，称其最高项的次数为这个多项式的度（degree），记作 $deg A$

对于多项式 $A(x), B(x)$，存在唯一的 $Q(x), R(x)$ 满足 $A(x) = Q(x)B(x) + R(x)$，其中 $deg R < deg B$，我们称 $Q(x)$ 为 $B(x)$ 除 $A(x)$ 的商，$R(x)$ 为 $B(x)$ 除 $A(x)$ 的余数，可以记作

\[ A(x) \equiv R(x) \pmod {B(x)} \]

BZOJ-2780. Sevenk Love Oimaster

题目给出 $n$ 个字符串 $s_1, s_2, \cdots, s_n$，以及 $m$ 个询问 $q_1, q_2, \cdots, q_m$，每个询问是一个字符串，要求计算 $q_i$ 在多少个 $s_1, s_2, \cdots, s_n$ 中出现过

例如 $s_1=abcabc, s_2=ca, s_3=a$，那么 $abc$ 在 $s_1$ 中出现过，$a$ 在 $s_1, s_2, s_3$ 中出现过

数据范围：$1 \leq n \leq 10^4, 1\leq q \leq 6\cdot 10^4, \sum_{i=0}^n |s_i| \leq 10^5, \sum_{i=0}^m |q_i| \leq 3.6 \cdot 10^5$

题目连接：BZOJ-2780、SPOJ-JZPGYZ

BZOJ-4001. [TJOI2015]概率论

题目要求出一个含有 $n$ 个节点的有序二叉树的叶子节点的期望个数，$n \leq 10^9$，要求精确到 $1.0 \times 10^{-9}$

例如一个含有 3 个节点的二叉树，一共有 5 种情况，期望的叶子节点个数是 $\frac{6}{5}$

BZOJ-3509. [CodeChef] COUNTARI

给定一个长度为 $n ~(1 \leq n \leq 10^5)$ 的数组 $a_i~(0 \leq a_i \leq 3\cdot 10^4)$，问有多少对 $(i, j, k)$ 满足 $i < j < k$ 且 $a_i - a_j = a_j - a_k$

也就是统计有多少对长度为 $3$ 的等差子序列（题目连接 BZOJ-3509, CodeChef COUNTARI）

例如 3 5 3 6 3 4 10 4 5 2，就有 (1, 3, 5), (1, 6, 9), (1, 8, 9), (3, 6, 9), (3, 8, 9), (5, 6, 9), (5, 8, 9), (4, 6, 10), (4, 8, 10) 一共 9 对

从多项式乘法到快速傅里叶变换

计算多项式的乘法，或者计算两个大整数的乘法是在计算机中很常见的运算，如果用普通的方法进行，复杂度将会是 $\mathcal O(n^2)$ 的，还有一种分治乘法可以做到 $\mathcal O(n^{\log_23})$ 时间计算（可以看这里）。下面从计算多项式的乘法出发，介绍快速傅里叶变换（Fast Fourier Transform, FFT）如何在 $\mathcal O(n\log n)$ 的时间内计算出两个多项式的乘积。

BZOJ-3771. Triple

这题挺有意思的，来源是 SPOJ-TSUM，题意大概是，给出 $n$ 个物品，第 $i$ 个物品的价值为 $x_i(0 < x_i \leq 4\cdot10^4)$，问在这 $n$ 个物品中选出 $1$ 个或 $2$ 个或 $3$ 个价值和是多少，对于每个价值求出方案个数，在这题中 $(a, b)$ 和 $(b, a)$ 算作一种方案。

例如有三个物品

选一个就可以得到 $1, 2, 3$ 三种价值

选两个就可以得到 $1+2, 1+3, 2+3$ 三种价值

选三个就可以得到 $1+2+3$ 一种价值

所以最后答案就是

区间 K 小问题

这篇文章将会介绍如何求解区间 K 小问题。