Menci

眉眼如初,岁月如故

在那无法确定的未来
只愿真心如现在一般清澈


  1. 「SDOI2015」序列统计 - 生成函数 + NTT

    小 C 有一个集合 S S ,里面的元素都是小于 M M 的非负整数。他用程序编写了一个数列生成器,可以生成一个长度为 N N 的数列,数列中的每个数都属于集合 S S

    小 C 用这个生成器生成了许多这样的数列。但是小 C 有一个问题需要你的帮助:给定整数 x x ,求所有可以生成出的,且满足数列中所有数的乘积 的值等于 x x 的不同的数列的有多少个。小 C 认为,两个数列 {Ai} \{ A_i \} {Bi} \{B_i\} 不同,当且仅当至少存在一个整数 i i ,满足 AiBi A_i \neq B_i 。另外,小 C 认为这个问题的答案可能很大,因此他只需要你帮助他求出答案 的值就可以了。

    于  BZOJ, FFT, NTT, SDOI, 原根, 快速幂, 数学, 生成函数 继续阅读

  2. 「ZJOI2014」力 - FFT

    已知

    Ei=Fiqi E_i = \frac{F_i}{q_i} Fj=i<jqiqj(ij)2i>jqiqj(ij)2 F_j = \sum\limits_{i < j} \frac{q_i q_j}{(i - j) ^ 2} - \sum\limits_{i > j} \frac{q_i q_j}{(i - j) ^ 2}

    求数列 E E

    于  BZOJ, FFT, ZJOI, 数学 继续阅读

  3. 「BZOJ 2194」快速傅立叶之二 - FFT

    给定两个长度为 n n 的序列 A A B B ,求长度为 n n 的序列 C C ,满足 Ck=i=kn1Ai×Bik C_k = \sum\limits_{i = k} ^ {n - 1} A_i \times B_{i - k}

    于  BZOJ, FFT, 数学 继续阅读

  4. FFT 学习笔记

    快速傅里叶变换(Fast Fourier Transform,FFT)是一种可在 O(nlogn) O(n \log n) 时间内完成的离散傅里叶变换(Discrete Fourier transform,DFT)算法,在 OI 中的主要应用之一是加速多项式乘法的计算。

    于  FFT, 多项式, 学习笔记, 数学, 算法模板 继续阅读