多项式部分简介
多项式是 OI 中一个既需要复杂的数学知识，又需要强大的代码能力的知识点。
学习方法
学习多项式，请：
- 搞懂数学推导过程（否则只能背结论）；
- 注意代码的细节，尤其是数组清零、参数的取值等；
- 将写好的模板封装起来，尽量避免使用函数外部数组，方便使用。
依赖关系
flowchart TD
%% 样式定义
classDef basic fill:#c9f7c9,stroke:#2e8b57,stroke-width:2px
classDef core fill:#b3e0ff,stroke:#0066cc,stroke-width:2px
classDef derived fill:#ffcc99,stroke:#ff6600,stroke-width:2px
classDef advanced fill:#e6ccff,stroke:#9933cc,stroke-width:2px
%% 基本运算（O(n)级别）
Add["加法
O(n)"]:::basic Sub["减法
O(n)"]:::basic Scale["数乘
O(n)"]:::basic Deriv["求导
O(n)"]:::basic Integral["积分
O(n)"]:::basic %% 核心乘法运算 Mult["乘法
FFT/NTT实现
O(n log n)"]:::core %% 依赖于乘法的运算 Inv["求逆
O(n log n)"]:::derived Div["除法
O(n log n)"]:::derived Sqrt["平方根
O(n log n)"]:::derived DivMod["带余除法
O(n log n)"]:::derived %% 依赖于乘法和基本运算的运算 Log["对数
O(n log n)"]:::derived Exp["指数
O(n log n)"]:::derived %% 更高级的运算 Pow["幂运算
O(n log n)"]:::advanced Sin["正弦
O(n log n)"]:::advanced Cos["余弦
O(n log n)"]:::advanced Tan["正切
O(n log n)"]:::advanced Asin["反正弦
O(n log n)"]:::advanced Acos["反余弦
O(n log n)"]:::advanced Atan["反正切
O(n log n)"]:::advanced %% 基本运算不依赖其他复杂运算 Add --> Mult Sub --> Mult Scale --> Mult %% 乘法是核心运算 Mult --> Inv Mult --> Div Mult --> Sqrt Mult --> Log Mult --> Exp %% 求逆和乘法的依赖 Inv --> Div Inv --> Sqrt Inv --> Asin Inv --> Acos %% 带余除法依赖于除法和乘法 Div --> DivMod Mult --> DivMod %% 求导和积分是基本运算 Deriv --> Log Deriv --> Asin Deriv --> Acos Deriv --> Atan Integral --> Log Integral --> Asin Integral --> Acos Integral --> Atan %% 对数和指数的依赖 Log --> Exp Log --> Pow Exp --> Pow Exp --> Sin Exp --> Cos Exp --> Tan %% 平方根的依赖 Sqrt --> Asin Sqrt --> Acos %% 三角函数的相互依赖 Sin --> Cos Sin --> Tan Cos --> Tan %% 反三角函数的依赖 Asin --> Acos %% 图例 - 使用单独节点表示 L1["基本运算 O(n)"]:::basic L2["核心运算 O(n log n)"]:::core L3["派生运算 O(n log n)"]:::derived L4["高级运算 O(n log n)"]:::advanced
O(n)"]:::basic Sub["减法
O(n)"]:::basic Scale["数乘
O(n)"]:::basic Deriv["求导
O(n)"]:::basic Integral["积分
O(n)"]:::basic %% 核心乘法运算 Mult["乘法
FFT/NTT实现
O(n log n)"]:::core %% 依赖于乘法的运算 Inv["求逆
O(n log n)"]:::derived Div["除法
O(n log n)"]:::derived Sqrt["平方根
O(n log n)"]:::derived DivMod["带余除法
O(n log n)"]:::derived %% 依赖于乘法和基本运算的运算 Log["对数
O(n log n)"]:::derived Exp["指数
O(n log n)"]:::derived %% 更高级的运算 Pow["幂运算
O(n log n)"]:::advanced Sin["正弦
O(n log n)"]:::advanced Cos["余弦
O(n log n)"]:::advanced Tan["正切
O(n log n)"]:::advanced Asin["反正弦
O(n log n)"]:::advanced Acos["反余弦
O(n log n)"]:::advanced Atan["反正切
O(n log n)"]:::advanced %% 基本运算不依赖其他复杂运算 Add --> Mult Sub --> Mult Scale --> Mult %% 乘法是核心运算 Mult --> Inv Mult --> Div Mult --> Sqrt Mult --> Log Mult --> Exp %% 求逆和乘法的依赖 Inv --> Div Inv --> Sqrt Inv --> Asin Inv --> Acos %% 带余除法依赖于除法和乘法 Div --> DivMod Mult --> DivMod %% 求导和积分是基本运算 Deriv --> Log Deriv --> Asin Deriv --> Acos Deriv --> Atan Integral --> Log Integral --> Asin Integral --> Acos Integral --> Atan %% 对数和指数的依赖 Log --> Exp Log --> Pow Exp --> Pow Exp --> Sin Exp --> Cos Exp --> Tan %% 平方根的依赖 Sqrt --> Asin Sqrt --> Acos %% 三角函数的相互依赖 Sin --> Cos Sin --> Tan Cos --> Tan %% 反三角函数的依赖 Asin --> Acos %% 图例 - 使用单独节点表示 L1["基本运算 O(n)"]:::basic L2["核心运算 O(n log n)"]:::core L3["派生运算 O(n log n)"]:::derived L4["高级运算 O(n log n)"]:::advanced
例题
提示：都是综合性的例题。
| 名称 | 编号 | 备注 | 题解 |
|---|---|---|---|