常用函数与定义 #include <bits/stdc++.h> using namespace std; #define SZ(x) ((int)(x).size()) typedef vector<int> VI; typedef long long ll; const int P = 998244353; void p…

有了多项式求逆和多项式乘法，以此为基础，可以类似前面 NTT 的做法写出各种函数。 #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> pll; typedef pair<int, int>…

常系数齐次递推 题目大意： 求一个满足 $k$ 阶齐次线性递推数列 $a_i$ 的第 $n$ 项，即： $$ a_n=\sum\limits_{i=1}^{k}f_i \times a_{n-i} $$ 第一行两个数 $n$,$k$；第二行 k 个数，表示 $f_1 \ f_2 \ \cdots \ f_k$；第三行 $k$ 个数，表示 $a_0 …

朴素积分 $$ \int_L^R\frac{cx+d}{ax+b}\mathrm{d}x $$ #include <bits/stdc++.h> using namespace std; typedef double db; typedef db func(db); db a, b, c, d, L, R; db f(db x) { r…

快速沃尔什变换 例题：P4717 【模板】快速沃尔什变换 (FWT) 题目描述 给定长度为 $2^n$ 两个序列 $A,B$，设 $$ C_i=\sum_{j\oplus k = i}A_j \times B_k $$ 分别当 $\oplus$ 是 or,and,xor 时求出 $C$ #include <bits/stdc++.h> …

杨辉三角 void init() { for (int i = 0; i < N; i++) { c[i][0] = 1; c[i][i] = 1; for (int j = 1; j < i; j++) c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % P; } } 线性推阶乘与阶乘逆元 int …

二项式定理 普通二项式定理： $$ (a+b)^n=\sum_{i=0}^n\binom{n}{i}a^{n-i}b^i $$ $$ \begin{pmatrix}m\cr 0\end{pmatrix}+\begin{pmatrix}m\cr 1\end{pmatrix}+\cdots+\begin{pmatrix}m\cr m\end{pmatr…

错位排列 对于 $1\sim n$ 的排列 $P$ 如果满足 $P_i\neq i$ ，则称 $P$ 是 $n$ 的错位排列。求 $n$ 的错位排列数。 递推式： 假设前 $n-1$ 个已经放好，第 $P_n$ 位置放了 $n$。如果前 $n-1$ 个已经是错位排序，则将 $P_n$ 与前面任意一个交换，可以产生一个 $n$ 的错位排序；如果前面只…

公式 定义： $$ h(n)=\sum_{i=0}^{n-1}h(i)b(n-1-i) $$ 生成函数： $$ F(x)=xF^{2}(x)+1=\frac{1-\sqrt{1-4x}}{2x} $$ 性质： $$ \begin{aligned} h(n)&=\frac{\binom{2n}{n}}{n+1}\cr h(n)&=C_…

第一类斯特林数 性质与结论 $\left[\begin{matrix} n \cr m \end{matrix}\right]$ 表示 $n$ 个不同的元素构成 $m$ 个圆排列的数目。 递推式：最后一个元素成单独一个圆排列，有$\left[\begin{matrix}n-1 \cr m-1 \end{matrix}\right]$种方案；若前$n…