菜鸡 Karry5307 的多项式题单 1

某些比较难的题目用 $\ast$ 标出来，建议有一定的水平之后再做。 ## 0x0 基础科技 > 当然，都是一些板子以及一些不用其他知识就能做出来的题。 ### 0x00 前置知识 推柿子能力，一些微积分，生成函数基础知识。 ### 0x01 FFT 与 NTT > 俗话说：万事开头难。 > > 为了在以后的题目中不被卡常，你需要一个比较快的 FFT，NTT 和 MTT 实现。 > > 后面也附了一些非模板题，这些题目只需要一些数学水平就可以做出。 - [Luogu P1919 【模板】A*B Problem升级版（FFT快速傅里叶）](https://www.luogu.com.cn/problem/P1919) - [Luogu P3803 【模板】多项式乘法（FFT）](https://www.luogu.com.cn/problem/P3803) - [Luogu P4245 【模板】任意模数NTT](https://www.luogu.com.cn/problem/P4245) - [Luogu P3338 [ZJOI2014]力](https://www.luogu.com.cn/problem/P3338) - [Luogu P3723 [AH2017/HNOI2017]礼物](https://www.luogu.com.cn/problem/P3723) - [Luogu P5488 差分与前缀和](https://www.luogu.com.cn/problem/P5488) - [Luogu P5641 【CSGRound2】开拓者的卓识](https://www.luogu.com.cn/problem/P5641)（真怀念 zhouwc 啊） ### 0x02 多项式求逆 > 求逆是一个非常重要的板子，以后很多题目都需要用到。 > > 当然，我们在这里说的“求逆”指的是乘法逆。 - [Luogu P4238 【模板】多项式乘法逆](https://www.luogu.com.cn/problem/P4238) - [Luogu P4239 任意模数多项式乘法逆](https://www.luogu.com.cn/problem/P4239) ### 0x04 多项式对指开根 > 三个后面会用到的板子。 > > 由于指数函数常数较大，你可能需要一个比较快的板子。 - [Luogu P4725 【模板】多项式对数函数（多项式 ln）](https://www.luogu.com.cn/problem/P4725) - [Luogu P4726 【模板】多项式指数函数（多项式 exp）](https://www.luogu.com.cn/problem/P4726) - [Luogu P5205 【模板】多项式开根](https://www.luogu.com.cn/problem/P5205) - [Luogu P5277 【模板】多项式开根（加强版）](https://www.luogu.com.cn/problem/P5277) ## 0x1 进阶科技 > 题目开始慢慢套路化了…… ### 0x10 倍增 FFT > 在某些动态规划题目中常常可以将 $n$ 转移到 $n+1$，或是转移到 $2n$，并且这两个转移都可以通过 FFT 来维护。 > >这个时候我们可以将 FFT 套上倍增以 $O(n\log^2n)$ 的复杂度通过。 - [CF755G PolandBall and Many Other Balls](https://www.luogu.com.cn/problem/CF755G)（鰰给出了一个 $O(k\log k)$ 的特征方程求通项做法，建议有了一定水平再来食用） - $\ast$ [CF623E Transforming Sequence](https://www.luogu.com.cn/problem/CF623E) - $\ast$ [CF773F Test Data Generation](https://www.luogu.com.cn/problem/CF773F) ### 0x11 分治 FFT > 分治 FFT 主要是用来求一些常规方法不好求的问题。 > > 当然，某些分治 FFT 题可以用生成函数大法以 $O(n\log n)$ 的复杂度通过。 - [Luogu P4721 【模板】分治 FFT](https://www.luogu.com.cn/problem/P4721) - $\ast$ [CF553E Kyoya And Train](https://www.luogu.com.cn/problem/CF553E) - $\ast$ [CF848E Days Of Floral Colours](https://www.luogu.com.cn/problem/CF848E) ### 0x12 背包问题 > 背包问题是最简单的一类生成函数问题，许多问题都可以建模成背包问题，并且可以使用一些技巧优化。 - [UVa12298 Super Poker](https://www.luogu.com.cn/problem/UVA12298) - [CF1251F Red-White Fence](https://www.luogu.com.cn/problem/CF1251F) - $\ast$ [Luogu P4389 付公主的背包](https://www.luogu.com.cn/problem/P4389) ## 0x2 组合计数 > 这里会涉及到使用一些特殊的数来进行给定式子的运算或者组合计数问题。 ### 0x20 斯特林数 > 两类斯特林数是两类常见的组合递推数列。 - [Luogu P5408 【模板】第一类斯特林数·行](https://www.luogu.com.cn/problem/P5408) - [Luogu P5409 【模板】第一类斯特林数·列](https://www.luogu.com.cn/problem/P5409) - [Luogu P5395 【模板】第二类斯特林数·行](https://www.luogu.com.cn/problem/P5395) - [Luogu P5396 【模板】第二类斯特林数·列](https://www.luogu.com.cn/problem/P5396) - [Luogu P4091 [HEOI2016/TJOI2016]求和](https://www.luogu.com.cn/problem/P4091)（EI 给出了线性做法，建议有了一定水平再来食用） - [CF960G Bandit Blues](https://www.luogu.com.cn/problem/CF960G)（$O(n\log^2n)$ 的做法可过） - $\ast$ [Luogu P5824 十二重计数法](https://www.luogu.com.cn/problem/P5824) ### 0x21 欧拉数 > 两类欧拉数是两类较常见的组合递推数列。 - [Luogu P5825 排列计数](https://www.luogu.com.cn/problem/P5825) - $\ast$ [Luogu P6073 [MdOI2020] Epic Convolution](https://www.luogu.com.cn/problem/P6073) ### 0x22 贝尔数 > 贝尔数 $B_n$ 的组合意义是将 $n$ 元素集划分成若干非空集合的方案数。 - [Luogu P5748 集合划分计数](https://www.luogu.com.cn/problemnew/show/P5748) ## 0x3 高级科技 ### 0x30 循环卷积，Bluestein's Algorithm 以及 FFT 本质优化 > 循环卷积的计算有些时候可以通过 FFT 的本质来优化。 > > Bluestein's Algorithm 主要通过把 $ij$ 拆开的方法来解决循环卷积的问题，或者是加速单位根反演的计算。 - $\ast$ [Luogu P5293 [HNOI2019]白兔之舞](https://www.luogu.com.cn/problemnew/show/P5293) - $\ast$ [CF901E Cyclic Cipher](https://www.luogu.com.cn/problem/CF901E) - $\ast$ [Luogu P4191 [CTSC2010]性能优化](https://www.luogu.com.cn/problem/P4191) - $\ast$ [CF1270I Xor on Figures](https://www.luogu.com.cn/problem/CF1270I) - $\ast$ [CF1103E Radix sum](https://www.luogu.com.cn/problem/CF1103E) ### 0x31 线性递推及其应用 > 常系数齐次线性递推有四种求法，你知道吗……？ - [Luogu P4723 【模板】常系数齐次线性递推](https://www.luogu.com.cn/problem/P4723) - $\ast$ [Luogu P3824 [NOI2017]泳池](https://www.luogu.com.cn/problem/P3824) ### 0x32 多点求值及其应用 > 多点求值算是一个比较有用的板子了。 - [Luogu P5050 【模板】多项式多点求值](https://www.luogu.com.cn/problem/P5050) - [Luogu P5158 【模板】多项式快速插值](https://www.luogu.com.cn/problem/P5158) - $\ast$ [Luogu P5808 【模板】常系数非齐次线性递推](https://www.luogu.com.cn/problem/P5808) - $\ast$ [CF1184A3 Heidi Learns Hashing (Hard)](https://www.luogu.com.cn/problem/CF1184A3) ### 0x33 下降幂多项式及其应用 > 下降幂多项式相比普通多项式在有限微积分上拥有更多的优点，可以使用有限微积分配合以解决某些普通多项式看起来不太好解决的问题。 - [Luogu P5383 普通多项式转下降幂多项式](https://www.luogu.com.cn/problem/P5383) - [Luogu P5393 下降幂多项式转普通多项式](https://www.luogu.com.cn/problem/P5393) - [Luogu P5394 【模板】下降幂多项式乘法](https://www.luogu.com.cn/problem/P5394) - $\ast$ [Luogu P5469 [NOI2019]机器人](https://www.luogu.com.cn/problem/P5469) ### 0x34 点值序列及其应用 > 跳出常规多项式的条条框框，用一个多项式的某些点值来代表整个多项式。这种点值序列的加减乘除运算都可以 $O(n)$ 解决，然而麻烦的是平移操作。 > > 利用点值序列的加减乘除和平移我们可以解决很多问题 - [Luogu P5667 拉格朗日插值2](https://www.luogu.com.cn/problem/P5667) - $\ast$ [Luogu P5282 【模板】快速阶乘算法](https://www.luogu.com.cn/problem/P5282) - $\ast$ [Luogu P5702 调和级数求和](https://www.luogu.com.cn/problem/P5702)