生成函数、多项式题单

生成函数、多项式题单 (大佬轻喷😭)

模板：

FFT/NTT 模板

用来测试多项式板子

• 多项式乘法：【模板】多项式乘法（FFT）

• 高精度乘法：A*B Problem 升级版

基础多项式全家桶模板

稍有难度的多项式板子

• 拉格朗日插值：【模板】拉格朗日插值

• MTT(任意模数多项式乘法)：【模板】任意模数多项式乘法

• 多项式或/与/异或卷积：【模板】快速莫比乌斯/沃尔什变换 (FMT/FWT)

• 分治 FFT/NTT：【模板】分治 FFT

• 多项式除法：【模板】多项式除法

• 多项式求逆：【模板】多项式乘法逆

• 多项式开根：

  • $a_0=1$ ：【模板】多项式开根
  • $a_0\ne 1$ ：【模板】多项式开根（加强版）

• 多项式 $\ln$：【模板】多项式对数函数（多项式 ln）

• 多项式 $\exp$：【模板】多项式指数函数（多项式 exp）

• 多项式快速幂：

  • $a_0=1$ ：【模板】多项式快速幂
  • $a_0\ne 1$ ：【模板】多项式幂函数（加强版）

进阶多项式全家桶模板

非常困难的的多项式板子

• 自然数幂前缀和：The Sum of the k-th Powers

• MTT 多项式求逆：任意模数多项式乘法逆

• 高阶差分/前缀和：差分与前缀和

• 子集卷积：【模板】子集卷积

• 十二重计数法：十二重计数法

• 多项式连续点值平移：拉格朗日插值2

• Chirp Z 变换：【模板】Chirp Z-Transform

• 多项式多点求值：【模板】多项式多点求值

• 多项式快速插值：【模板】多项式快速插值

• 多项式复合函数：【模板】多项式复合函数

• 多项式复合函数求逆：【模板】多项式复合逆

• 下降幂多项式：

  • 下降幂多项式乘法：【模板】下降幂多项式乘法
  • 下降幂多项式与普通幂多项式的互相转换：
    • 普通多项式转下降幂多项式
    • 下降幂多项式转普通多项式

• 斯特林数：

  • 第一类斯特林数·行
  • 第一类斯特林数·列
  • 第二类斯特林数·行
  • 第二类斯特林数·列

• 分拆数：分拆数

• 贝尔数：集合划分计数

• 欧拉数：排列计数

• 快速求阶乘：【模板】快速阶乘算法

• 快速求调和级数：调和级数求和

• 一阶微分方程：一阶微分方程

• 常系数齐次线性递推：【模板】常系数齐次线性递推

• 常系数非齐次线性递推：【模板】常系数非齐次线性递推

• 整式递推：【模板】整式递推

• 多项式三角函数：多项式三角函数

• 多项式反三角函数：多项式反三角函数

题目：

生成函数/多项式基础题：

比较好推的生成函数/多项式题目

• Dice Sum
• [NOIP2012 普及组] 摆花
• Blocks
• 挑选队友
• Reordering
• msc的背包
• Product Tuples
• Thief in a Shop
• Lucky Tickets
• Needle
• Counting Sequences
• Snake

生成函数/多项式提高题：

比较难或者需要一些多项式科技的生成函数/多项式题目，还有一些集合幂级数的题目

• Function analysis
• One to One
• Tree Coloring
• Fly
• The Child and Binary Tree
• 付公主的背包
• Falfa with Substring
• Easy Counting Problem
• Equipment Upgrade
• Count Set
• 带权子集和
• Odd Sum
• [TJOI2019]唱、跳、rap和篮球
• [省选联考 2020 A 卷] 组合数问题
• Forest
• NIO’s OAuth2 Server
• Lndjy and the mex
• [TJOI2018]教科书般的亵渎
• Cargo
• Differential Equation
• Expectation (Hard Version)

ICPC/CCPC 区域赛生成函数/多项式题目：

题目之间难度差别较大

• 2017 CCPC 杭州：Marriage

• 2018 CCPC 桂林：Array Modify

• 2018 ICPC 沈阳：Renaissance Past in Nancy

• 2019 ICPC 上海网络赛：Counting Sequences II、Triple

• 2019 ICPC 南昌现场赛：XOR Sum

• 2019 ICPC 南昌网络赛：Interesting Series

• 2019 ICPC 南昌邀请赛：Polynomial

• 2020 ICPC 澳门：Accelerator、Fly Me To The Moon

• 2020 ICPC 沈阳：United in Stormwind

• 2021 CCPC 威海：810975、Shinyruo and KFC

• 2021 CCPC 广州：Math Ball、Unnamed Easy Problem

• 2021 CCPC 江苏省赛：Five Phases

• 2021 ICPC 上海：Strange Permutations

• 2021 ICPC 澳门：Pass the Ball!

• 2021 ICPC 济南：Strange Series

• 2022 CCPC 广东省赛：拉格朗日插值

• 2022 CCPC 江苏省赛：Pockets、Super Gray Pony

• 2022 CCPC 桂林：Alice’s Dolls

• 2022 CCPC 女生赛：Devil May Cry