一些数学套路

组合数学

一个经常考的式子,类似于和式的交换求和顺序 \[ \binom{n}{m}\binom{m}{k}=\binom{n}{k}\binom{n-k}{m-k} \] 范德蒙德卷积,通常来说看出来需要一定的技巧,理解起来就是分开成两个集合来选 \[ \sum_{i=0}^k\binom{n}{i}\binom{m}{k-i}=\binom{n+m}{k} \] 一个比较巧妙的式子,\(i\) 表示枚举断点,为了去重所以断点一定要选 \[ \sum_{i=0}^{n}\binom{i}{x}\binom{n-i}{y}=\binom{n+1}{x+y+1} \] 考得少但考到就凉凉的式子,大概意思是到坐标 \((i-m,m)\) 的方案数和相当于再往右走一格再一直向上 \[ \sum_{i=m}^n\binom{i}{m}=\binom{n+1}{m+1} \] 卡特兰数通常用来计数式子类似 \(f_n=\sum_{i=0}^nf_i\times f_{n-i-1}\) \[ C_n=\binom{2n}{n}\frac{1}{n+1} \] \(Raney\) 引理: 设整数序列 \(a_1,a_2\dots a_n\)\(\sum_{i=1}^na_i=1\) ,那么对于每一种序列恰有一种循环方式使得任意前缀和均为正数

可以考虑用该引理来证明卡特兰数递推式

多项式与生成函数

点值多项式转下降幂多项式

如果题目给出一个 \(m\) 次多项式的 \(f(0)\)\(f(m)\) 的点值,那么可以考虑将该多项式转成下降幂多项式来推导式子

具体的,设 \(F(x)\) 为下降幂多项式,\(f(x)\) 表示多项式在 \(x\) 处的点值,\(f_i\) 满足 \[ F(x)=\sum_{i=0}^mf_ix^{\underline i}\\ \] 那么有 \[ f(x)=\sum_{i=0}^mf_i\frac{x!}{(x-i)!}\\ \frac{f(x)}{x!}=\sum_{i=0}^mf_i\frac{1}{(x-i)!} \] 将等式左边看为一个最高项为 \(m\)\(EGF\) ,等式右边看为下降幂多项式的系数组成的最高项为 \(m\)\(OGF\)\(e^x\) 做卷积,注意,这个等式初始只对 \(x\in[0,m]\) 有效,所以看为生成函数后等式只在前 \(m+1\) 项是等价的,后面的项没有意义

所以可以通过用点值表示出来的 \(EGF\)\(e^{-x}\) 做卷积后前 \(m+1\) 项即为 \(f_i\)

当然,如果给出的是普通多项式的话,可以用多点求值得到点值后再转为下降幂多项式

任意基DFT

用来求解诸如 \(a_i=\sum_{j=0}^n b_j\times \omega^{ij}\) 的每一项,\(i\in[0,m]\),因为有 \[ ij=\binom{i+j}{2}-\binom{i}{2}-\binom{j}{2} \] 所以 \[ \begin{align} a_i&=\sum_{j=0}^n b_j\times \omega^{\binom{i+j}{2}-\binom{i}{2}-\binom{j}{2}}\\ &=\omega^{\binom{i}{2}}\sum_{j=0}^n b_j\times \omega^\binom{j}{2}\times \omega^\binom{i+j}{2} \end{align} \]\[ \begin{align} A_i&=b_i\times \omega^\binom{i}{2}\\ B_i&=\omega^{n+m-i} \end{align} \] 那么有 \[ a_i=\omega^{\binom{i}{2}}\times \sum_{j=0}^nA_j\times B_{n+m-i-j} \] 注意到 \(A\) 数组只在 \([0,n]\) 范围类有值,所以可以松弛上界为 \[ a_i=\omega^{\binom{i}{2}}\times \sum_{j=0}^{n+m-i}A_j\times B_{n+m-i-j} \] 这是一个卷积的形式,发现没有用到单位根的任何性质,所以 \(\omega\) 可以为任意数