点值表示法 对于一个 $n-1$ 阶多项式 $P (x)=a_0+a_1x+a_2x^2+\cdots+a_{n-1} x^{n-1}$，如果我们已知一个点集 $S:\{(x_0,y_0),(x_1,y_1),\cdots,(x_{n-1},y_{n-1})\}$，点集 $S$ 中的所有点都满足 $y_i=P (x_i)$，且 $x_i (i=0,1,\c…

ABC214G - Three Permutations 题解 这题做了一万年，最后也算是想出了一个比较强大的模型转换。。。 给定两个大小为 $N$ 的排列 $P,Q$ ，询问满足以下条件的排列 $R$ 的数量： 对于任意 $i\in [1, N]$ 均满足 $R_i\neq P_i \cap R_i\neq Q_i$ 。 $N\leq 3000$…

这一章节主要通过各种例题的形式幂级数解法，来演示第一章节中的解题思维（或者说将题目翻译成多项式语言？）如何转化为算法实现。 前置芝士 首先你需要知道的是一些常用的多项式化简方法和多项式基本操作。 二项式定理 $$(x+y)^n=\sum_{i=0}^n \binom {n}{i} x^iy^{n-i}$$ 等比数列求和 $$\sum_{i=0}^{n-…

题目来源：AIsing Programming Contest 2020 F - Two Snuke 已知：$s_2>s_1,n_2>n_1,u_2>u_1,k_2>k_1,e_2>e_1$ 且均为非负整数，计算： \begin {aligned} \sum_{s_1 + s_2 + n_1 + n_2 + u_1 + …

题目来源：ACL Beginner Contest F - Heights and Pairs。 给定一个大小为 $2N$ 的数组 $H$ ，要求将 $H$ 中的元素两两匹配，使得恰好构成 $N$ 个数对 $(H_i,H_j)$ 满足 $H_i\neq H_j$ 。 $N\leq 50000, H_i\leq 100000$ 。 首先容易想到通过容…

多项式基本操作 多项式加法、减法 有手就行。 多项式乘法 一句话概括，就是 FFT。 这是整个多项式章节中最基础的一部分：如何用 FFT 将两个 $n$ 度的多项式乘法优化到 $O (n\log n)$ 的时间复杂度。 洛谷模板题：P3803 【模板】多项式乘法（FFT），P4245 【模板】任意模数多项式乘法 。 在多项式乘法中，有两个核心问题，加法卷积…

本文主要讨论形式幂级数在解决数学问题以及算法竞赛问题的思维，因此并不会涉及形式幂级数运算的编程实现。 例题引入 [admonition title="问题 1" color="indigo"] 有 $3$ 个集合 $A=\{2,3\}, B=\{2,4\},C=\{3,5,7\}$ ，现在要求从三个集合中各选择恰好一个元素 $a,b,c$ 使得 $a+…