首页

2026-03-08T07:18:22Z

33DAI：

<div class="main-page-welcome" style="padding: 20px; background: #f8f9fa; border-radius: 8px; margin-bottom: 20px;">
欢迎来到 '''三三百科'''！这里汇集了信奥常用小知识、比赛题解、以及常用工具导航。
</div>

<div class="main-page-grid">
{{NavBox
| title = Wiki 数学
| color = #ab5a6b
| icon = ✨
| content =
* [[乘法逆元]]
* [[质数判断]]
* [[欧拉函数]]
* [[计算几何]]
* [[高精度模板]]
* [[线段树模板]]
}}

{{NavBox
| title = Wiki 页面
| color = #ab5a6b
| icon = ✨
| content =
* [[基础语法大纲]]
* [[初学者常用内容]]
* [[STL容器库常用内容]]
* [[STL例子]]
* [[33OJ评测机]]
* [[33OJ题面规范]]
}}

{{NavBox
| title = 常用 OJ 平台
| color = #27ae60
| icon = 🚀
| content =
* [https://oj.33dai.cn 33OJ]
* [https://luogu.com.cn 洛谷]
* [https://codeforces.com CodeForces]
* [https://atcoder.jp AtCoder]
* [https://htoj.hetao101.com/cpp/ 核桃周赛]
* [https://bs.daimayuan.top/ 代码源挑战赛]
}}

{{NavBox
| title = 信息查询
| color = #e67e22
| icon = 📚
| content =
* [https://www.noi.cn NOI 官网]
* [https://ioinformatics.org/ IOI官网]
* [https://board.xcpcio.com/ XCPC榜单]
* [https://oier.baoshuo.dev/ OIerDB]
* [http://oiwiki.org/ OI Wiki]
* [https://oeis.org/ OEIS]
}}

{{NavBox
| title = 常用工具
| color = #8e44ad
| icon = 🛠️
| content =
* [https://cpp.33dai.wiki C++ 参考手册]
* [https://py.33dai.wiki Python 文档]
* [https://visualgo.net/zh/ VISUALGO]
* [https://csacademy.com/app/graph_editor/ Graph Editor]
* [https://www.geogebra.org/graphing GeoGebra]
* [https://github.com/open33oj/wiki33 原"三三文档"内容]
}}

</div>

<pre>
<pre>([\s\S\n\r]*?)</pre>
<syntaxhighlight lang="cpp" line>$1</syntaxhighlight>
</pre>

线段树模板

2026-03-08T06:59:41Z

33DAI：创建页面，内容为“==单点修改区间查询== <syntaxhighlight lang="cpp" line> const int MAXN = 500000; struct SegTree { int sum[MAXN * 4 + 5]; // 根据子节点算当前节点 void up(int now) { sum[now] = sum[now * 2] + sum[now * 2 + 1]; } // 基于 a 数组 build void build(int a[], int now, int l, int r) { if (l == r) { sum[now] = a[l]; return; } int mid = (l + r) / 2;…”

初学者常用内容

2026-03-07T03:07:19Z

33DAI：

补充中
==编译指令==

===Windows===

Windows 修改语言标准及开栈编译命令为 -std=c++14 -O2 -Wl,--stack=1073741824

其中 -Wl,--stack=1073741824 在某些场景可能需要双引号括起来。

===Linux===

Linux 当前会话开栈命令为 ulimit -s unlimited

可以用 ulimit -s 查看栈空间大小。

==保留 3 位小数==

<syntaxhighlight lang="cpp" line>
cout << fixed << setprecision(3) << 1.0 / 3;
</syntaxhighlight>

==最大公因数/最小公倍数==

比赛时允许使用 C++ 自带的 {{ic|code=__gcd(a,b)}} 函数求最大公因数。

<syntaxhighlight lang="cpp" line>
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
int lcm(int a, int b)
{
return a / gcd(a, b) * b;
}
</syntaxhighlight>

==判断质数==

===判断单个质数===

* 如果小于 <math>2</math> 肯定不是质数
* 检查 <math>2\sim \sqrt{n}</math>，如果有因子，肯定不是质数
* 通过了前面的检查就肯定是质数

===筛法===

核心都是对于质数 <math>p</math> 与任意数 <math>i</math>，把 <math>p\times i</math> 标记为合数。

* 埃氏筛法：<math>O(n\log \log n)</math> 把筛出来的质数的倍数标记为合数。
* 欧拉筛法：<math>O(n)</math> 把每个数的质数倍标记为合数，如果当前质数是因子，就不用考虑更大的质数了（肯定会可以由一个更大的数乘以那个作为因子的质数）

欧拉筛法能保证每个数只被最小质因子筛，可以用来处理一些积性函数求解。

==广搜核心逻辑==

# 多测要清空
# 起点入队
# 重复取出队头并扩散

==动态规划经典思路==

# 大胆猜测状态
## 求最大长度：“前 i 项的最大长度”、“以第 i 项结尾的最大长度”
## 求方案数：“前 i 项的方案数”、“以第 i 项结尾的方案数”
## 求最大收益：“前 i 个物品的最大收益”
## 求最少操作次数：“s 的前 i 项与 t 的前 j 项的最少操作次数”
# 大胆猜测决策
## 选不选第 i 项
## 上一项选谁
# 不好求就加维度
## 前 i 个物品的最大收益：前 i 个物品在 j 体积下的最大收益

三三月赛

2026-03-01T03:25:47Z

33DAI：创建页面，内容为“==难度== 大约 CSP-J 级别，参考 [https://oj.33dai.cn/p?q=category%3A%E6%9C%88%E8%B5%9B 33OJ:月赛] ==赛制== OI 赛制 ==比赛时长== 3 小时 ==比赛时间== * 正赛（线下断网赛）：每个月倒数第二个周六晚 18:00 * 线上镜像赛：每个月最后一个周末持续开放 ==比赛费用== * 正赛：128 元/场或按一次训练营收费。 * 线上镜像赛：免费在 [https://oj.33dai.cn 33OJ] 参与。 ==出题人==…”

==难度==

大约 CSP-J 级别，参考 [https://oj.33dai.cn/p?q=category%3A%E6%9C%88%E8%B5%9B 33OJ:月赛]

==赛制==

OI 赛制

==比赛时长==

3 小时

==比赛时间==

* 正赛（线下断网赛）：每个月倒数第二个周六晚 18:00
* 线上镜像赛：每个月最后一个周末持续开放

==比赛费用==

* 正赛：128 元/场或按一次训练营收费。
* 线上镜像赛：免费在 [https://oj.33dai.cn 33OJ] 参与。

==出题人==

独立第三方出题人，不公开身份。

* 出题人 A
** ICPC 区域赛金牌
** CodeForces Rating 2157
** 多次命题 ICPC 省赛、邀请赛
** 出题场次：2603

反演

2026-02-28T09:26:36Z

33DAI：/* 狄利克雷卷积 */

本页面大量引用 [https://oiwiki.org/ OI Wiki]

组合数 <math>C_n^m</math> 常用符号 <math>\dbinom{n}{m}</math> 来表示，读作“<math>n</math> 选 <math>m</math>”。

==组合数经典性质==

选出 <math>m</math> 相当于选出 <math>n-m</math> 个排除。

<math>\dbinom{n}{m}=\dbinom{n}{n-m}</math>

组合数的递推式（杨辉三角）

<math>\dbinom{n}{m}=\dbinom{n-1}{m}+\dbinom{n-1}{m-1}</math>

基础性质（杨辉三角的一行、<math>(1+1)^n</math>）

<math>\dbinom{n}{0}+\dbinom{n}{1}+\dots+\dbinom{n}{n}=\sum_{i=0}^n\dbinom{n}{i}=2^n</math>

范德蒙德恒等式

<math>\sum_{i=0}^k\dbinom{n}{i}\dbinom{m}{k-i}=\dbinom{m+n}{k}</math>

==二项式定理==

<math>(a+b)^n=\sum_{i=0}^n\dbinom{n}{i}a^{n-i}b^i</math>

==二项式反演==

记 <math>f_n</math> 表示恰好使用 <math>n</math> 个不同元素形成特定结构的方案数，<math>g_n</math> 表示从 <math>n</math> 个不同元素中选出 <math>i \geq 0</math> 个元素形成特定结构的总方案数．

若已知 <math>f_n</math> 求 <math>g_n</math>，那么显然有：

<math>g_n = \sum_{i = 0}^{n} \binom{n}{i} f_i</math>

若已知 <math>g_n</math> 求 <math>f_n</math>，那么：

<math>f_n = \sum_{i = 0}^{n} \binom{n}{i} (-1)^{n-i} g_i</math>

上述已知 <math>g_n</math> 求 <math>f_n</math> 的过程，就称为“二项式反演”．

==狄利克雷卷积==

数论函数 <math>f(n)</math> 和 <math>g(n)</math> 的 Dirichlet 卷积（Dirichlet convolution），记作 <math>f \ast g</math>，定义为数论函数

<math>
(f \ast g)(n) = \sum_{k\mid n}f(k)g\left(\dfrac{n}{k}\right) = \sum_{k\ell=n}f(k)g(\ell).
</math>

==莫比乌斯反演==

===莫比乌斯函数===

莫比乌斯函数（Möbius 函数）定义为

<math>
\mu(n)=
\begin{cases}
1,&n=1,\\
0,&n\text{是某个质数平方的倍数},\\
(-1)^k,&n \text{是} k \text{个不同质数的乘积}.\\
\end{cases}
</math>

具体地，假设正整数 <math>n</math> 有素因数分解 <math>n=\prod_{i=1}^kp_i^{e_i}</math>，其中，<math>p_i</math> 是素数，<math>e_i</math> 是正整数．那么，三种情形分别对应：

# <math>\mu(1) = 1</math>；
# 当存在 <math>i</math> 使得 <math>e_i>1</math>，即存在任何素因数出现超过一次时，<math>\mu(n)=0</math>；
# 否则，对于所有 <math>i</math> 都有 <math>e_i = 1</math>，即任何素因数都只出现一次时，<math>\mu(n)=(-1)^k</math>，其中，$k$ 就是互异素因子的个数．

===莫比乌斯反演===
设 <math>f(n),g(n)</math> 是两个数论函数．那么，有

<math>
f(n) = \sum_{d\mid n}g(d) \iff g(n) = \sum_{d\mid n}\mu\left(\dfrac{n}{d}\right)f(d).
</math>

====扩展====

<math>
f(n) = \sum_{n\mid d}g(d) \iff g(n) = \sum_{n\mid d}\mu\left(\dfrac{d}{n}\right)f(d).
</math>

[[文件:莫比乌斯反演.jpg|缩略图|替代=莫比乌斯反演|莫比乌斯反演]]

反演

2026-02-28T09:05:55Z

33DAI：/* 扩展 */

本页面大量引用 [https://oiwiki.org/ OI Wiki]

组合数 <math>C_n^m</math> 常用符号 <math>\dbinom{n}{m}</math> 来表示，读作“<math>n</math> 选 <math>m</math>”。

==组合数经典性质==

选出 <math>m</math> 相当于选出 <math>n-m</math> 个排除。

<math>\dbinom{n}{m}=\dbinom{n}{n-m}</math>

组合数的递推式（杨辉三角）

<math>\dbinom{n}{m}=\dbinom{n-1}{m}+\dbinom{n-1}{m-1}</math>

基础性质（杨辉三角的一行、<math>(1+1)^n</math>）

<math>\dbinom{n}{0}+\dbinom{n}{1}+\dots+\dbinom{n}{n}=\sum_{i=0}^n\dbinom{n}{i}=2^n</math>

范德蒙德恒等式

<math>\sum_{i=0}^k\dbinom{n}{i}\dbinom{m}{k-i}=\dbinom{m+n}{k}</math>

==二项式定理==

<math>(a+b)^n=\sum_{i=0}^n\dbinom{n}{i}a^{n-i}b^i</math>

==二项式反演==

记 <math>f_n</math> 表示恰好使用 <math>n</math> 个不同元素形成特定结构的方案数，<math>g_n</math> 表示从 <math>n</math> 个不同元素中选出 <math>i \geq 0</math> 个元素形成特定结构的总方案数．

若已知 <math>f_n</math> 求 <math>g_n</math>，那么显然有：

<math>g_n = \sum_{i = 0}^{n} \binom{n}{i} f_i</math>

若已知 <math>g_n</math> 求 <math>f_n</math>，那么：

<math>f_n = \sum_{i = 0}^{n} \binom{n}{i} (-1)^{n-i} g_i</math>

上述已知 <math>g_n</math> 求 <math>f_n</math> 的过程，就称为“二项式反演”．

==狄利克雷卷积==

==莫比乌斯反演==

===莫比乌斯函数===

莫比乌斯函数（Möbius 函数）定义为

<math>
\mu(n)=
\begin{cases}
1,&n=1,\\
0,&n\text{是某个质数平方的倍数},\\
(-1)^k,&n \text{是} k \text{个不同质数的乘积}.\\
\end{cases}
</math>

具体地，假设正整数 <math>n</math> 有素因数分解 <math>n=\prod_{i=1}^kp_i^{e_i}</math>，其中，<math>p_i</math> 是素数，<math>e_i</math> 是正整数．那么，三种情形分别对应：

# <math>\mu(1) = 1</math>；
# 当存在 <math>i</math> 使得 <math>e_i>1</math>，即存在任何素因数出现超过一次时，<math>\mu(n)=0</math>；
# 否则，对于所有 <math>i</math> 都有 <math>e_i = 1</math>，即任何素因数都只出现一次时，<math>\mu(n)=(-1)^k</math>，其中，$k$ 就是互异素因子的个数．

===莫比乌斯反演===
设 <math>f(n),g(n)</math> 是两个数论函数．那么，有

<math>
f(n) = \sum_{d\mid n}g(d) \iff g(n) = \sum_{d\mid n}\mu\left(\dfrac{n}{d}\right)f(d).
</math>

====扩展====

<math>
f(n) = \sum_{n\mid d}g(d) \iff g(n) = \sum_{n\mid d}\mu\left(\dfrac{d}{n}\right)f(d).
</math>

[[文件:莫比乌斯反演.jpg|缩略图|替代=莫比乌斯反演|莫比乌斯反演]]

2026-02-28T06:10:51Z

33DAI：/* 莫比乌斯反演 */

本页面大量引用 [https://oiwiki.org/ OI Wiki]

组合数 <math>C_n^m</math> 常用符号 <math>\dbinom{n}{m}</math> 来表示，读作“<math>n</math> 选 <math>m</math>”。

==组合数经典性质==

选出 <math>m</math> 相当于选出 <math>n-m</math> 个排除。

<math>\dbinom{n}{m}=\dbinom{n}{n-m}</math>

组合数的递推式（杨辉三角）

<math>\dbinom{n}{m}=\dbinom{n-1}{m}+\dbinom{n-1}{m-1}</math>

基础性质（杨辉三角的一行、<math>(1+1)^n</math>）

<math>\dbinom{n}{0}+\dbinom{n}{1}+\dots+\dbinom{n}{n}=\sum_{i=0}^n\dbinom{n}{i}=2^n</math>

范德蒙德恒等式

<math>\sum_{i=0}^k\dbinom{n}{i}\dbinom{m}{k-i}=\dbinom{m+n}{k}</math>

==二项式定理==

<math>(a+b)^n=\sum_{i=0}^n\dbinom{n}{i}a^{n-i}b^i</math>

==二项式反演==

记 <math>f_n</math> 表示恰好使用 <math>n</math> 个不同元素形成特定结构的方案数，<math>g_n</math> 表示从 <math>n</math> 个不同元素中选出 <math>i \geq 0</math> 个元素形成特定结构的总方案数．

若已知 <math>f_n</math> 求 <math>g_n</math>，那么显然有：

<math>g_n = \sum_{i = 0}^{n} \binom{n}{i} f_i</math>

若已知 <math>g_n</math> 求 <math>f_n</math>，那么：

<math>f_n = \sum_{i = 0}^{n} \binom{n}{i} (-1)^{n-i} g_i</math>

上述已知 <math>g_n</math> 求 <math>f_n</math> 的过程，就称为“二项式反演”．

==狄利克雷卷积==

==莫比乌斯反演==

===莫比乌斯函数===

莫比乌斯函数（Möbius 函数）定义为

<math>
\mu(n)=
\begin{cases}
1,&n=1,\\
0,&n\text{ is divisible by a square }>1,\\
(-1)^k,&n\text{ is the product of }k\text{ distinct primes}.\\
\end{cases}
</math>

具体地，假设正整数 <math>n</math> 有素因数分解 <math>n=\prod_{i=1}^kp_i^{e_i}</math>，其中，<math>p_i</math> 是素数，<math>e_i</math> 是正整数．那么，三种情形分别对应：

# <math>\mu(1) = 1</math>；
# 当存在 <math>i</math> 使得 <math>e_i>1</math>，即存在任何素因数出现超过一次时，<math>\mu(n)=0</math>；
# 否则，对于所有 <math>i</math> 都有 <math>e_i = 1</math>，即任何素因数都只出现一次时，<math>\mu(n)=(-1)^k</math>，其中，$k$ 就是互异素因子的个数．

2026-02-28T02:34:24Z

33DAI：/* 二项式定理 */

反演

2026-02-28T02:31:37Z

33DAI：/* 组合数经典性质 */

2026-02-12T08:16:49Z

33DAI：

补充中

==保留 3 位小数==

<syntaxhighlight lang="cpp" line>
cout << fixed << setprecision(3) << 1.0 / 3;
</syntaxhighlight>

==最大公因数/最小公倍数==

比赛时允许使用 C++ 自带的 {{ic|code=__gcd(a,b)}} 函数求最大公因数。

<syntaxhighlight lang="cpp" line>
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
int lcm(int a, int b)
{
return a / gcd(a, b) * b;
}
</syntaxhighlight>

==判断质数==

===判断单个质数===

* 如果小于 <math>2</math> 肯定不是质数
* 检查 <math>2\sim \sqrt{n}</math>，如果有因子，肯定不是质数
* 通过了前面的检查就肯定是质数

===筛法===

核心都是对于质数 <math>p</math> 与任意数 <math>i</math>，把 <math>p\times i</math> 标记为合数。

* 埃氏筛法：<math>O(n\log \log n)</math>把筛出来的质数的倍数标记为合数。
* 欧拉筛法：<math>O(n)</math>把每个数的质数倍标记为合数，如果当前质数是因子，就不用考虑更大的质数了（肯定会可以由一个更大的数乘以那个作为因子的质数）

欧拉筛法能保证每个数只被最小质因子筛，可以用来处理一些积性函数求解。
==广搜核心逻辑==

# 多测要清空
# 起点入队
# 重复取出队头并扩散

==动态规划经典思路==

# 大胆猜测状态
## 求最大长度：“前 i 项的最大长度”、“以第 i 项结尾的最大长度”
## 求方案数：“前 i 项的方案数”、“以第 i 项结尾的方案数”
## 求最大收益：“前 i 个物品的最大收益”
## 求最少操作次数：“s 的前 i 项与 t 的前 j 项的最少操作次数”
# 大胆猜测决策
## 选不选第 i 项
## 上一项选谁
# 不好求就加维度
## 前 i 个物品的最大收益：前 i 个物品在 j 体积下的最大收益

初学者常用内容

2026-02-12T06:36:12Z

33DAI：