几度风雨几度春秋 风霜雪雨博激流
历尽苦难痴心不改 少年壮志不言愁

分类 算法 下的文章

五边形数定理用来描述欧拉函数展开式的特性:

\varphi(x) = \prod_{n=1}^\infty (1 - x^n) = \sum_{k=-\infty}^{\infty} (-1)^k x^{\frac {k(3k+1)} 2} = \sum_{k=0}^{\infty} (-1)^k x^{\frac {k(3k \pm 1)} 2}

欧拉函数的倒数是划分数的生成函数:

\frac 1 {\varphi(x)} = \sum_{i=0}^\infty p(i) x^i = \prod_{i=0}^\infty \sum_{j=0}^\infty x^{ij} = \prod_{i=0}^\infty \frac 1 {1 - x^i}

READ MORE

伯努利数的定义

  • 递推定义

    \sum_{i=0}^n B_i \binom {n+1} i = 0 \ (n > 0) \\ \Leftrightarrow \\ B_{m+1} = [m=0] - \sum_{i=0}^m \binom {m+1} i B_i \\ \Leftrightarrow \\ [m=0] = \sum_{i=0}^{m+1} \binom {m+1} i B_i
  • 生成函数定义 \frac x {e^x - 1} = \sum_{n=0}^\infty B_n \frac {x^n} {n!}

READ MORE

ZJOI 2019 了,机房同学也差不多都会基本多项式了,就写篇有关简单的多项式操作复习笔记吧 QAQ

约定:以下操作默认 n = \deg(F(x)) + 1 ,等号一般表示在 \bmod\ {x^n} 的意义下同余。

多项式乘法

可以先把多项式的系数转为点值,各位分别乘起来以后再插值出原多项式。考虑到单位根 / 原根的性质,我们有 FFT / NTT 。

READ MORE

写于:2019-01-13 20:44

更新于:2019-03-16 11:45

二项式反演:

\begin{aligned} f_n=\sum_{i=0}^{n}(-1)^i {n \choose i} g_i &\Leftrightarrow g_n=\sum_{i=0}^{n}(-1)^i {n \choose i} f_i \\ f_n=\sum_{i=0}^{n}{n \choose i} g_i &\Leftrightarrow g_n=\sum_{i=0}^{n}(-1)^{n-i} {n \choose i} f_i \end{aligned}

READ MORE