OI Wiki 学习地图 · 第 6 章 高阶路径:数学

OI Wiki 学习地图 · 第 6 章 高阶路径:数学

章节摘要:本章进入高阶,讲数学(docs/math/ 113篇,OI Wiki 最庞大的部分)。数论(筛法/莫比乌斯反演/杜教筛)、多项式 docs/math/poly/ FFT/NTT/FWT 难点精讲(★)、线性代数、组合数学、概率论。数学是 OI Wiki 最深的章节,本章重点精讲多项式(复数域DFT/数论变换NTT/位运算卷积FWT)。本章共 3 节,前置依赖为第 1-5 章。

路径坐标

高阶(本章) → 省选/IOI(第7章)

学习目标

1. 掌握数论(筛法/欧拉函数/乘法逆元)。
2. 理解莫比乌斯反演与杜教筛。
3. 理解 FFT/NTT/FWT 多项式运算(★)。
4. 了解线性代数/组合/概率在竞赛的应用。

子章节导航

01 数论(对应 docs/math/number-theory/)

素数判定/筛法(埃氏/欧拉线性);欧拉函数/费马小定理;乘法逆元(费马/扩展欧几里得);中国剩余定理CRT;莫比乌斯反演(莫比乌斯函数/反演公式/整除分块);杜教筛(数论函数前缀和O(n^2/3));引用 docs/math/number-theory/ 33篇。

02 多项式难点精讲 ★

FFT docs/math/poly/fft.md(复数域/DFT离散傅里叶变换/蝶形运算/分治NTT思路);NTT docs/math/poly/fft-ntt.md(数论变换/原根替代单位根/模数998244353);FWT docs/math/poly/fwt.md(位运算卷积/或/与/异或变换);多项式运算(乘法/求逆/开方/对数/指数/牛顿迭代);慢节奏精讲FFT蝶形运算;引用 docs/math/poly/ 16篇。

03 线性代数/组合/概率(对应 docs/math/)

矩阵运算/矩阵快速幂(加速递推);高斯消元;线性基;组合数学(排列组合/卢卡斯定理/卡特兰数);概率期望DP;博弈论(Nim游戏/SG函数);引用 docs/math/ 其他子目录。

前置知识与后续延伸

前置:第1-5章(DP基础用于概率DP)。后续:第7章(多项式用于进阶算法)。