Candy Piles

「AGC 002E」Candy Piles

题目大意

有 $n$ 个数，两人玩游戏，每次可以取最大的变 $0$ 或把所有的非零数减 $1$，把全部的数变 $0$ 的人会输，问是否先手必胜。

数据范围：$n \le 10^5$。

目录

本文包括 IOI 2020 集训队作业 19 ~ 24 题的题解。下面是题单：

• 19.「AGC 026F」Manju Game
• 20.「AGC 027D」Modulo Matrix
• 21.「AGC 027E」ABBreviate
• 22.「AGC 027F」Grafting
• 23.「AGC 028C」Min Cost Cycle
• 24.「AGC 028D」Chords

简介

本文包括 IOI 2020 集训队作业 13 ~ 18 题的题解。下面是题单：

• 13.「AGC 024F」Simple Subsequence Problem
• 14.「AGC 025D」Choosing Points
• 15.「AGC 025E」Walking on a Tree
• 16.「AGC 025F」Addition and Andition
• 17.「AGC 026D」Histogram Coloring
• 18.「AGC 026D」Synchronized Subsequence

杜教筛

杜教筛可以快速求一些积性函数的前缀和。假设我们要求 $S(n) = \sum_{i = 1}^{n} f(i)$，杜教筛方法如下：

$$\begin {align*} & \sum_{i = 1}^{n} (f * g)(i) = \sum_{i = 1}^{n} g(i) S(\lfloor \frac{n}{i} \rfloor) \\ \Leftrightarrow \ & g(1) S(n) = \sum_{i = 1}^{n} (f * g)(i) + \sum_{i = 2}^{n} g(i) S(\lfloor \frac{n}{i} \rfloor) \end {align*}$$

简介

本文包括 IOI 2020 集训队作业第 7 到 12 题的题解。

• 「AGC 022E」 Median Replace
• 「AGC 022F」 Checkers
• 「AGC 023D」 Go Home
• 「AGC 023F」 01 on Tree
• 「AGC 024D」 Isomorphism Freak
• 「AGC 024E」 Sequence Growing Hard

第一类斯特林数

第一类斯特林数 $s(n, m)$ 表示长度为 $n$ 的置换有 $m$ 个环的方案数。

第一类斯特林数有递推式 $s(n, m) = s(n - 1, m - 1) + s(n - 1, m) \times (n - 1)$，（讨论第 $n$ 个数新开一个环或者接在之前某个数后面），还有 $s(n, m) = \sum_{i = 1}^n s(n - i, m - 1) \times (i - 1)! \times C(n - 1, i - 1)$（枚举第一个数所在的环的大小，并考虑其他数的排法）。

可以用分治 FFT 在 $O(n \log^2 n)$ 的时间内求出第一类斯特林数的一行。

简介

长链剖分是一种树链剖分，与重链剖分不同的是，每个点的关键儿子是它向下高度最大的儿子。

长链剖分有许多优美的性质。例如，某个点的 $k$ 级祖先所在链的边数一定不小于 $k$；任意两点之间只会跨过 $\sqrt n$ 条链。另外，长链剖分还可以在线性的时间内解决状态规模为子树高度的许多 dp。

前言

以后的博客中可能会有一些计算几何的内容。

李超线段树已经在路上了。

又水了一篇博客呢

目录

• Problem A. 奇怪装置

• Problem B. 桥梁

• Problem C. 路灯