简介

准确的说，杂题整理……

~~一些闪耀着光芒的题~~

「codechef JULY19B GUESSPRM」Guess the Prime!

题目描述

$S h e f$ 选了 $2$ 到 $10^{9}$ 之间的一个素数 $P$ ，要你猜它

在你给出你的猜测之前，你可以问 $S h e f$ 最多 $2$ 个问题

在每个问题中，你给 $S h e f$ 一个整数 $x (1 \leq x \leq 10^{9})$ ，然后 $S h e f$ 会告诉你 $x^{2} mod P$ 的值

然后，你开始猜 $S h e f$ 的素数 $P$ ，他会告诉你你的猜测是否正确

然而， $S h e f$ 有时会作弊：他可以在任意时候改变他选定的素数（即使在你告诉他你的猜测之后），但他会保证改变后他之前对你问的所有问题的回答都还是正确的

向 $S h e f$ 展示你总能猜到正确的素数的能力，即使他试图作弊！

社论

~~eoj猜个p加强版~~

~~你可以假设他不会变自己的素数~~

找两个数字 $x, y$ ，然后分别求出来 $a = x^{2} mod p, b = y^{2} mod p$

考虑 $gcd (x^{2} - a, y^{2} - b) = k p$ ，那么分解质因数，依次判断是否满足 $x^{2} mod p^{'} = a, y^{2} mod p^{'} = b$

~~随便生成一些 $x, y$ ，本机拍拍就出来了~~

「BJOI2014」想法

题目描述

小强和阿米巴是好朋友。小强要出一套题目。

他的题目以涉及面广（偏）、考察深入（怪）、思维强度大（难）著称。他为了出题，一共攒了 $M$ 个本质不同的想法，每个想法形成了一个题目。不过，他觉得拿这些题目去考察选手会把比赛搞的太过变态，所以，想请阿米巴来帮忙调整一下他的题目。

阿米巴指出，为了让一场考试的题目的考察点尽量全面，有一个通用的做法叫做「组合」。如果把两个题目 $A$ 和 $B$ 组合在一起，那么组合而成的题目涉及到的想法的集合就是 $A$ 涉及到的想法的集合和 $B$ 涉及到的想法的集合的并。

并且，题目是可以反复组合的。

例如，小强现在有三个想法 $1, 2, 3$ ，分别对应了题目 $P_{1}, P_{2}, P_{3}$ 。

现在，小强把 $P_{1}$ 和 $P_{2}$ 组合得到 $P_{4}$ 。 $P_{4}$ 涉及的想法的集合是 $1, 2$ 。

之后，小强把 $P_{2}$ 和 $P_{3}$ 组合得到 $P_{5}$ 。 $P_{5}$ 涉及的想法的集合是 $2, 3$ 。

最后，小强把 $P_{4}$ 和 $P_{5}$ 组合得到 $P_{6}$ 。 $P_{6}$ 涉及的想法的集合是 $1, 2, 3$ 。

现在，小强告诉你每个题目都是如何组合而来的。你要回答的就是，每个题目涉及的想法的集合有多大。

不过，这个问题是很难的。于是，你只需要能够以比较高的概率回答的比较准确即可。

第一行两个整数 $N$ ， $M$ ，依次表示小强的题目数量和想法的数量。

接下来 $N - M$ 行，每行两个整数，依次表示小强组合出来的题目都是由哪两个题组合而成的。 $M$ 个想法对应的题目依次编号为 $1 \sim M$ 。之后，小强组合出来的第一个题编号为 $M + 1$ ，组合出来的第二个题编号为 $M + 2$ ，依次类推。

输出 $N - M$ 行，每行一个整数表示小强组合出来的每个题都涉及了几个想法。

对于所有数据， $M \leq 10^{5}, N \leq 10^{6}$ 。

对于每个输出文件，如果其中你有 $95$ 以上的行的答案和正确答案的误差不超过 $25$ ，那么你就可以得到分数。所谓误差不超过 $25$ ，即，如果正确答案是 $X$ ，那么你的答案在 $[0.8 X, 1.25 X]$ 这个闭区间内。

社论

~~为什么省选会有这种题啊~~

考虑到不需要求出正确答案，近似的就好

一个引理：

在 $[0, 1]$ 随机选 $n$ 个实数，第 $k$ 小的期望值是 $\frac{k}{n + 1}$

考虑把每个 $1 \sim m$ 的题都打上一个随机权，这样对每个题都有一个它所包含的集合的最小值

设值域为 $D$ ，最小值为 $e$ ，则 $\frac{D}{n + 1} = e$ ，也就是 $n = \frac{D}{e} - 1$

这个 $e$ 可以多跑几次取平均值

「雅礼集训 2017 Day11」PATH

题目描述

给定 $n$ 和 $a_{i}$ ，满足 $a_{0} \geq a_{1} \geq \dots \geq a_{n - 1} \geq 0$

求出在 $n$ 维空间中从 $(0, 0, \dots, 0)$ 走到 $(a_{0}, a_{1}, \dots, a_{n - 1})$ ，每一步使某一维坐标增加 $1$ 的方案中随机选出一种

满足经过的所有点 $(x_{0}, x_{1}, \dots, x_{n - 1})$ 都满足 $x_{0} \geq x_{1} \geq \dots \geq x_{n - 1}$ 的概率

答案模 $1004535809$ 输出，其中 $n, a_{i} \leq 500000$

社论

先考虑一下分母吧，也就是有多少种随机游走的方案（注意，这里只是要求第 $i$ 维不超过 $a_{i}$ ）

不难发现它就是个多重集合排列（要求第 $i$ 维内部有序）

记 $m = \sum_{i = 1}^{n} a_{i}$ ，则总方案就是：

$\frac{m!}{\prod_{i = 1}^{n} a_{i}!}$

考虑分子，也就是合法的游走方案数

这玩意在二维情况下叫做卡特兰数（ $x \geq y$ 的游走方案数）

高维情况下，可以把每一维横着画长度为 $a_{i}$ 的序列，然后就在这个上面走轮廓线的意思

如果把每个格子的访问时间写出来，就是一个标准杨表的形式，也就是相当于求 $(a_{1}, a_{2}, \dots, a_{n})$ 的本质不同标准杨表个数

然而上面那玩意太鬼畜了，用数学化的语言描述就是，设第 $i$ 维，值为 $j$ 的时间为 $f_{i, j}$ ，那么要求每一行递增（维度内有序），以及每一列递增（不同维度成单调）

不管怎么说还是回到了杨表计数……

~~感觉这玩意也只能做个求概率了……因为上面那个 $m!$ 是让你求个 $(n \cdot max a_{i})!$ 之类的鬼畜玩意……~~

根据钩子公式，可以得到分子的一个表达：

$\frac{m!}{\prod_{1 \leq i, j \leq n} h_{a} (i, j)}$

然而这个没啥用，因为它是 $n^{2}$ 的……

它的用 $a$ 表达的形式为：

$\frac{m! \prod_{1 \leq i < j \leq n} ((a_{i} - i) - (a_{j} - j))}{\prod_{i = 1}^{n} (a_{i} + n - i)!}$

记 $b_{i} = a_{i} + n - i$ ，则可写作：

$\frac{m! \prod_{1 \leq i < j \leq n} (b_{i} - b_{j})}{\prod_{i = 1}^{n} b_{i}!}$

把分母除下去，得：

$\begin{aligned} \frac{\frac{m! \prod_{1 \leq i < j \leq n} (b_{i} - b_{j})}{\prod_{i = 1}^{n} b_{i}!}}{\frac{m!}{\prod_{i = 1}^{n} a_{i}!}} \\ = & (\prod_{i = 1}^{n} \frac{a_{i}!}{b_{i}!}) (\prod_{1 \leq i < j \leq n} (b_{i} - b_{j})) \end{aligned}$

然后就只需要计算后面那个东西了

然后如果直接这么转化的话就凉了……似乎只能 $O (n \log^{2} n)$ 的自闭玩意做

还是展开比较好：

$\prod_{1 \leq i < j \leq n} ((a_{i} - i) - (a_{j} - j))$

~~由于 $a_{i} \geq a_{i + 1}$ ，因此 $(a_{i} - i) - (a_{j} - j) = (a_{i} - a_{j}) + (j - i) \geq 0$~~

~~也就是说这个 $i < j$ 的限制是没用的……（木大木大木）~~

~~然后就可以忽略掉这个限制来做 $n t t$ 了~~

~~然而感觉这个似乎有点偏差啊……实际上最后算答案是需要枚举权值，然后得到它的出现次数，把 $x^{y}$ 贡献进去~~

~~换句话说，这个出现次数应该是模的 $ϕ (p)$ 啊？~~

~~而且出现次数是 $n^{2}$ 级别的？这个模了 $p$ 后真的不会出事吗……~~

~~实际上系数大部分都是 $1$ ，因此卷积完后是 $O (n)$ 级别的……~~

~~也许可以证明吧~~

考虑到 $a_{i} - i$ 是不增的，也就是 $(a_{i} - i) - (a_{j} - j) \geq 0$

那么如果能凑出大于 $0$ 的数，当且仅当 $i < j$

也就是直接忽略掉 $i < j$ 后跑 $n t t$ ，然后只使用大于 $0$ 的部分即可

~~一个可能只有我踩到的坑点：若 $p = a \times 2^{b} + c$ 的话，则数组最多用到 $2^{b}$~~

这部分的实现可以先把需要用到的最小值搞出来，然后都减去这个最小值后 $n t t$ ，最后偏移回去即可

「雅礼集训 2018 Day4」Cube

题目描述

众所周知，正方形有 $4$ 个点， $4$ 条边；正方体有 $8$ 个点， $12$ 条边， $6$ 个面

定义点为零维基础图形，线段为一维基础图形，正方形为二维基础图形，正方体为三维基础图形……

那么请问，一个 $n$ 维基础图形包含多少个 $m$ 维基础图形呢 $(m \leq n)$ ？

多次询问，输出对 $998244353$ 取模，其中 $T \leq 10^{5}, 0 \leq m \leq n \leq 10^{5}$

社论

考虑一下点到底是个啥东西

定义 $n$ 维基础图形的顶点为， $n$ 维向量中每一维是 $0 / 1$ 的向量集合

比如说正方体上的顶点就是 $(0 / 1, 0 / 1, 0 / 1)$

那么把点再往多扩展一下，不难发现， $m$ 维基础图形在 $n$ 维基础图形上的表现为，某些维取值相同，剩下维取值唯一（是个 $m$ 维基础图形）

因此答案就是 $(\binom{n}{n - m}) 2^{n - m}$

EntropyIncreaser 与 Minecraft

题目描述

求 $\sum_{i = 1}^{n} | x_{i} | \leq p$ 的方案数，其中 $x_{i} \in Z$ ，答案模 $10^{9} + 7$ ，其中 $n, p ⩽ 10^{6}$

社论

首先枚举有多少个 $0$ ，那么剩下的（假设剩下了 $k$ 个数）要求它的绝对值大于 $0$ ，这样的话方案数就是 $2^{k}$

考虑设 $y_{i} = x_{i} + 1$ ，其中 $x_{i} \geq 0$ ，则需要求如下方程的方案数：

$\sum_{i = 1}^{k} y_{i} \leq p \Rightarrow \sum_{i = 1}^{k} x_{i} \leq p - k$

众所周知，对于 $\sum_{i = 1}^{k} x_{i} = p$ 的方案数为 $(\binom{k + p - 1}{k - 1})$

也就是说，总方案为：

$\sum_{k = 0}^{n} (\binom{n}{k}) 2^{k} \sum_{i = 0}^{p} (\binom{k + i - k - 1}{k - 1})$

注意到 $k = 0$ 的时候答案是 $1$ ，要特殊处理一下（冒出来一个 $k - 1$ ）

然后把它化简一下：

$\sum_{k = 0}^{n} (\binom{n}{k}) 2^{k} \sum_{i = 0}^{p - 1} (\binom{i}{k - 1})$

注意到 $\sum_{i = 0}^{n} (\binom{i}{m}) = (\binom{n + 1}{m + 1})$ ，因此上面那个玩意就是：

$\sum_{k = 0}^{n} (\binom{n}{k}) 2^{k} (\binom{p}{k})$

~~好了这回就不需要特判了~~

惠和惠惠和惠惠惠

题目描述

你在二维坐标系下，一开始你在 $(0, 0)$ ，每次你可以使用三个方向向量之一（即 $(1, 1), (1, 0), (1, - 1)$ 这三个），同时你只能在第一象限或坐标轴上，且在 $n$ 次操作后，你需要到达 $(n, 0)$ ，同时要求恰好碰触 $x$ 轴 $k$ 次（包括一开始的时候和结束的时候）

求方案数，答案模 $998244353$ ，其中 $1 \leq n, k \leq 10^{5}$

社论

设 $f_{i, j}$ 表示走到了 $(i, 0)$ 的方案数，不难得到 $f_{i, j} = \sum_{t = 0}^{i - 1} f_{t, j - 1} g_{i - j}$ ，起始状态为 $f_{0, 1} = 1$ ，答案就是 $f_{n, k}$

其中 $g (n)$ 表示从 $(0, 0)$ 走到 $(n, 0)$ ，且 $k = 2$ 时的方案数

考虑另一个东西，即 $h (n)$ ，也就是从 $(0, 0)$ 走到 $(n, 0)$ 且不能走到第四象限的方案数

这玩意叫 Motzkin numbers（你并不需要知道这是什么）

显然有 $g (n) = h (n - 2)$ ，因为开头和结尾必须一个往上一个往下（ $n$ 比较小的时候有特例）

为了不重不漏的计数，那么只需要在除了 $(0, 0)$ 外第一次处于 $x$ 轴的位置处计数即可

则有：
$h (n) = h (n - 1) + \sum_{i = 2}^{n} h (i - 2) h (n - i)$
即：
$h (n) = h (n - 1) + \sum_{i = 0}^{n - 2} h (i) h (n - 2 - i)$
生成函数为：
$\begin{aligned} H (x) = x H (x) + x^{2} H^{2} (x) + 1 \\ \Rightarrow & x^{2} H (x)^{2} + (x - 1) H (x) + 1 = 0 \\ \Rightarrow & H (x) = \frac{(1 - x) \pm \sqrt{(x - 1)^{2} - 4 x^{2}}}{2 x^{2}} \\ \Rightarrow & H (x) = \frac{(1 - x) \pm \sqrt{1 - 2 x - 3 x^{2}}}{2 x^{2}} \end{aligned}$
由于要求 $H (0) = 1$ ，那么如果取加号，则上面为 $2$ ，下面为 $\infty$

因此取负号时，满足 $H (0) = 1$

考虑生成函数，设 $f_{*, j} = f_{j} (x)$ ，不难得到 $f_{1} (x) = 1$

同时有 $f_{j} (x) = (x + x^{2} h (x)) \times f_{j - 1} (x) \Rightarrow f_{j} (x) = (x + x^{2} h (x))^{j - 1}$

由于 $h (x) = \frac{1 - x - \sqrt{1 - 2 x - 3 x^{2}}}{2 x^{2}}$ ，所以：

$\begin{aligned} f_{j} (x) = & (x + x^{2} h (x))^{j - 1} \\ = & {(x + \frac{1 - x - \sqrt{1 - 2 x - 3 x^{2}}}{2})}^{j - 1} \\ = & {(\frac{1 + x - \sqrt{1 - 2 x - 3 x^{2}}}{2})}^{j - 1} \end{aligned}$

多项式开根是不可能开根的，~~这辈子都不可能多项式开根的~~

考虑 $H (x) = \frac{1 - x - \sqrt{1 - 2 x - 3 x^{2}}}{2 x^{2}}$ 的形式幂级数的系数

存在三个一次多项式 $A (x), B (x), C (x)$ ，满足 $A (n) h_{n} = B (n - 1) h_{n - 1} + C (n - 2) h_{n - 2}$

而且它们的系数都不大，直接 $O (20^{6})$ 暴搜即可

显然那个系数不大的结论是在对着结论说过程，正经做法在这：一类通过生成函数求线性递推式的方法

这个做法目前为止的时间复杂度为 $O (m \log m + m^{3} + n m)$ 的

其中 $m = (D + 1) (L + 1)$ ，在这个数据范围下，有 $D = 2, L = 3$

所涉及的知识点：多项式初步，打表找规律（说好听点就是归纳总结），高斯消元，离线求逆元

算法难度：noip提高组（大雾）

~~并不需要 $N T T$ 等高深的多项式算法~~

考虑到实际上是让你求：

${(\frac{1 + x - \sqrt{1 - 2 x - 3 x^{2}}}{2})}^{k - 1}$

不难发现它是一个整式递推数列

说人话就是，相比于线性递推数列，它前面的系数从常数扩展到了一个多项式

举个例子，某个整式递推数列也许长这样：

$A (n) f_{n} = B (n - 1) f_{n - 1} + C (n - 2) f_{n - 2}$

不妨将它一般化，假设递推长度为 $L$ ，系数多项式的最高次数为 $D$ ，则有：

$\sum_{i = 0}^{L} \sum_{j = 0}^{D} f_{n - i} (n - i)^{j} e_{i, j} = 0$

$e_{i}$ 就对应着第 $i$ 个系数多项式

然后就可以高斯消元了，不过很可惜它是线性相关的，也就是你可能有很多解

不过一般来说，在这类问题中，它一定是一个基解乘以常数构成的解集

也就是说如果碰到了一个自由元，就随便给它赋个随机数，然后继续消元

注意你的目标是 $e_{0}$ 不是 $0$

然后你就可以在 $O ((L D)^{3})$ 的时间复杂度内搞出一组递推函数

之后还原这个序列的时候就这么递推过去就行了，注意到要求逆，这里可能比叫恶心

不过在模素数意义下， $f_{n}$ 前面的系数又不是 $0$ ，可以直接 $O (n)$ 离线求逆元

回到这个题，会发现这个形式幂级数会有 $k$ 个前缀 $0$ ，所以你得弄 $O (k)$ 项

同时发现这个内层多项式的常数项为 $0$ ，一次项系数为 $1$ ，也就是它是 $(x A (x))^{k - 1} = x^{k - 1} A (x)^{k - 1}$

诶不过我们只需要知道非 $0$ 的递推就行了，也就是说只需要从第 $k$ 项开始跑快速幂就行了

换而言之这个时间复杂度是 $O (m \log m + m^{3} + n m)$ 的

「雅礼集训 2018 Day4」Divide

神仙题……orz ImagineC

显然跟 $w$ 的顺序无关

考虑把 $w$ 按照某种方式进行重新定序，然后对于 $i$ ，对于所有的 $1 \leq j < i$ ，要么都满足 $w_{i} + w_{j} \geq m$ ，要么都满足 $w_{i} + w_{j} < m$

这样的话，就可以把 $i$ 放到 $A$ 或 $B$ 时都可以进行计算答案了

假设已经排好序了，设 $f_{i, j}$ 表示考虑完了前 $i$ 个人，其中 $| A | = j$ 时的最大答案（显然方案数可以在更新 $f$ 时顺便更新）

如果对于所有的 $1 \leq j < i$ ，都满足 $w_{i} + w_{j} \geq m$ ，则如果 $i$ 放到 $A$ ，则会对 $B$ 中所有的人产生贡献，反之亦然

即：

$f_{i, j} = max (f_{i - 1, j - 1} + (i - j), f_{i - 1, j} + j)$

否则，无论 $i$ 放到 $A$ 还是放到 $B$ ，则一定不会对答案产生影响，即：

$f_{i, j} = max (f_{i - 1, j - 1}, f_{i - 1, j})$

那么剩下的问题就是如何对 $w$ 进行重新定序

考虑先对 $w$ 升序排序，看一下 $w_{1}$ 和 $w_{n}$ 的关系，如果 $w_{1} + w_{n} \geq m$ ，则对于任意的 $1 \leq i < n$ ，都有 $w_{i} + w_{n} \geq m$

此时把 $w_{n}$ 放到最终序列的末尾即可，剩下就是一个子问题 $[1, n - 1]$

如果 $w_{1} + w_{n} < m$ ，那么对于任意 $2 \leq i \leq n$ ，都有 $w_{1} + w_{i} < m$ ，因此把 $w_{1}$ 放到序列末尾，然后递归处理 $[2, n]$ 即可

「Wannafly挑战赛26」msc的棋盘

题目描述

给定 $b_{m}$ ，求有多少个不同的 $a_{n}$ ，满足存在一个填上了一些棋子的 $n \times m$ 的网格图，满足第 $i$ 行的棋子个数为 $a_{i}$ ，第 $j$ 列的棋子个数为 $b_{j}$

答案模 $10^{9} + 7$ ，其中 $n, m \leq 50$

社论

好神仙的东西啊……orz ImagineC

~~网络流计数（大雾）~~

考虑如果给定了 $a_{n}$ 和 $b_{m}$ ，怎么判断这个 $n \times m$ 的棋盘是否合法

考虑网络流建图，源点向行连流量为 $a_{i}$ 的边，列向汇点连流量为 $b_{i}$ 的边

对于行 $i$ 和列 $j$ ，连 $i \to j$ 的流量为 $1$ 的边

如果最后流量为 $\sum b_{i}$ ，当然也应该是等于 $\sum a_{i}$ 的，则此棋盘合法

由于最大流等于最小割，只需要最小割为 $\sum b_{i}$ 即可

考虑这张网络流的图，它一共分成了四层

由于要求是一个割集，因此如果在 $S \to r o w$ 割了 $i$ 条边，且在 $c o l u m n \to T$ 割了 $j$ 条边，则还需要在 $r o w \to c o l u m n$ 中割 $(n - i) (m - j)$ 条边（因为需要 $S, T$ 不连通，且割的边的权值之和尽量小）

由于中间的边的权值都是 $1$ ，因此左右两端应该尽可能地选较小的，也就是从小到大按照权值排序后选一个前缀

假设 $a_{n}$ 和 $b_{m}$ 都从小往大排好序了，记前缀和分别为 $s_{a}, s_{b}$ ，那么最小割就是：

$min_{0 \leq i \leq n, 0 \leq j \leq m} s_{a_{i}} + s_{b_{j}} + (n - i) (m - j)$

首先它肯定能达到 $\sum b_{i}$ 的，因为只需要让 $i = 0, j = m$ 即可

由于最小割是 $\sum b_{i}$ ，因此只需要对于任意的取值，让它都不低于其即可

也就是如果合法，当且仅当：

$(min_{0 \leq i \leq n, 0 \leq j \leq m} s_{a_{i}} + s_{b_{j}} + (n - i) (m - j)) \geq s_{b_{m}}$

注意到还有一个条件就是横纵的棋子个数应相等，即 $\sum a_{i} = \sum b_{i}$

可以先通过枚举 $i, j$ ，来算出 $s_{a_{i}}$ 的最小值

然后就可以 $d p$ 了，设 $f_{i, j, k}$ 表示最大值不超过 $i$ 时，已经填了 $j$ 行，已经填的 $a$ 的和是 $k$ 的方案数

转移则可以枚举填了多少个 $i + 1$ ，有：

$f_{i, j, k} (\binom{n - j}{t}) \to f_{i + 1, j + t, k + (i + 1) t}$

「雅礼集训 2017 Day11」DIV

题目描述

定义复数 $a + b i$ 为整数 $k$ 的约数，当且仅当 $a$ 和 $b$ 为整数且存在整数 $c$ 和 $d$ 满足 $(a + b i) (c + d i) = k$

给定 $n$ ，求出 $1$ 到 $n$ 的所有满足 $a > 0$ 的约数 $a + b i$ 的 $a$ 的和

答案模 $1004535809$ 输出，其中 $n \leq 10^{10}$

社论

orz 11Dimensions

~~开局一个主函数，剩下函数全靠Lambda~~

若 $(a + b i) (c + d i) = n$ ，则：

${\begin{cases} a c - b d = n \\ a d + b c = 0 \end{cases}$

对于第二个式子，即：

$\frac{a}{b} = - \frac{c}{d}$

设 $gcd (p, q) = 1$ ，且 $\frac{a}{b} = - \frac{c}{d} = \frac{p}{q}$ ，可得：

$(a + b i) (c + d i) = b (\frac{p}{q} + i) d (- \frac{p}{q} + i) = n$

替换一下，可得：

$x (p + q i) y (p - q i) = n = x y (p^{2} + q^{2})$

先考虑虚部大于 $0$ 的情况，然后枚举 $k = p^{2} + q^{2}$ ，记录 $x p$ 的贡献，有：

$\begin{aligned} \sum_{k} \sum_{p^{2} + q^{2} = k \land gcd (p, q) = 1} p \sum_{k | T} \sum_{x | \frac{T}{k}} x \\ = & \sum_{k} \sum_{p^{2} + q^{2} = k \land gcd (p, q) = 1} p \sum_{k | T} σ_{1} (\frac{T}{k}) \\ = & \sum_{k} \sum_{p^{2} + q^{2} = k \land gcd (p, q) = 1} p \cdot D (⌊ \frac{n}{k} ⌋) \end{aligned}$

其中 $D$ 是 $σ_{1}$ 的前缀和，即：

$D (n) = \sum_{i = 1}^{n} σ_{1} (i) = \sum_{i = 1}^{n} i \cdot ⌊ \frac{n}{i} ⌋$

考虑对 $⌊ \frac{n}{k} ⌋$ 除法分块，然后就只需要求这个：

$f (k) = \sum_{p^{2} + q^{2} = k \land gcd (p, q) = 1} p$

设 $F (k) = \sum_{i \leq k} f (i)$ ，再让 $G (k)$ 为不需要满足 $gcd (p, q) = 1$ 的 $F$ ，则：

$G (k) = \sum_{d \geq 1} d \cdot F (⌊ \frac{k}{d^{2}} ⌋)$

即：

$F (k) = G (k) - \sum_{d \geq 2} d \cdot F (⌊ \frac{k}{d^{2}} ⌋)$

同时有：

$G (k) = \sum_{p^{2} + q^{2} = k} p = \sum_{p = 1}^{⌊ \sqrt{k} ⌋} p \cdot ⌊ \sqrt{k - p^{2}} ⌋$

虚部小于 $0$ 的和上面的等价，直接乘 $2$ 即可

还剩下虚部为 $0$ 的情况，此时答案为：

$\begin{aligned} \sum_{a} a \sum_{c} [a c \leq i] \\ = & \sum_{i = 1}^{n} σ_{1} (i) \\ = & D (n) \end{aligned}$

「雅礼集训 2018 Day10」文明

题目描述

给定一棵树，若干次询问，每次给定 $k$ 个点 $a_{1} \sim a_{k}$ ，一共会进行无限轮游戏，按照 $1 \sim k$ 的顺序进行

每次每个人会把当前他所在的连通块往外扩展距离 $1$ ，当然如果碰到其他人就不会往那里扩展

求 $a_{1}$ 最多能扩展多少，其中 $n, q \leq 5 \times 10^{5}, 1 \leq k_{i} \leq n, \sum k_{i} \leq 10^{6}$

社论

显然不能达到的点构成了一些连通块（子树之类的）

那么对于所有的 $j \geq 2$ ，求一下 $a_{1} \to a_{j}$ 的往右中点（靠 $a_{j}$ 的那个点）

然后把这些点加上 $a_{1}$ 建虚树，然后求一下从 $a_{1}$ 距离为 $1$ 的这些点，然后把它们的不靠近 $a_{1}$ 的子树大小之和即可

答案就是 $n$ 减去无法到达的连通块

auto lambda 一时爽，一直这啥一直爽

一个很有效的常数优化：倍增数组的 f[N][20]，要写成 f[20][N]，然后就快了 $0.5 s$ 了

「20190710」抽卡

题目描述

你在抽卡，你每次有 $p (0 < p \leq 1)$ 的概率抽到特殊角色，一共有 $n$ 种特殊角色

如果你连续 $L - 1$ 次没抽到特殊角色，那么在下一次时必定抽到特殊角色

求抽到 $n$ 种特殊角色的期望次数（如果某次恰好凑齐了 $n$ 种，则立即停止）

答案模 $998244353$ ，其中 $1 \leq n \leq L < 998244353$

社论

~~一场模拟赛，两个计数，一个照着结论出题，这是人干的事啊……~~

对于脸黑的限制，不妨枚举抽出 $i - 1$ 张牌的期望次数，然后最多再抽 $L$ 次就能抽到

即：

$f_{c} = (1 - p)^{L - 1} (\frac{n - c}{n} (f_{c + 1} + L) + \frac{c}{n} (f_{c} + L)) + \sum_{i = 1}^{L - 1} (1 - p)^{i - 1} p (\frac{n - c}{n} (f_{c + 1} + i) + \frac{c}{n} (f_{c} + i))$

化简一下：

$\begin{aligned} f_{c} = & (1 - p)^{L - 1} (\frac{n - c}{n} f_{c + 1} + \frac{c}{n} f_{c} + L) \\ + & \sum_{i = 1}^{L - 1} (1 - p)^{i - 1} p (\frac{n - c}{n} f_{c + 1} + \frac{c}{n} f_{c} + i) \\ = & (1 - p)^{L - 1} (\frac{n - c}{n} f_{c + 1} + L) \\ + & (1 - p)^{L - 1} \frac{c}{n} f_{c} \\ + & (\sum_{i = 1}^{L - 1} (1 - p)^{i - 1} p (\frac{n - c}{n} f_{c + 1} + i)) \\ + & (\sum_{i = 1}^{L - 1} (1 - p)^{i - 1} p) \frac{c}{n} f_{c} \end{aligned}$

其中有：

$\sum_{i = 1}^{L - 1} (1 - p)^{i - 1} p = p \sum_{i = 0}^{L - 2} (1 - p)^{i} = p \frac{1 - (1 - p)^{L - 1}}{p} = 1 - (1 - p)^{L - 1}$

则有：

$(1 - p)^{L - 1} + 1 - (1 - p)^{L - 1} = 1$

于是有：

$\begin{aligned} f_{c} = & \frac{c}{n} f_{c} + (1 - p)^{L - 1} (\frac{n - c}{n} f_{c + 1} + L) + \sum_{i = 1}^{L - 1} (1 - p)^{i - 1} p (\frac{n - c}{n} f_{c + 1} + i) \\ = & \frac{(1 - p)^{L - 1} (\frac{n - c}{n} f_{c + 1} + L) + \sum_{i = 1}^{L - 1} (1 - p)^{i - 1} p (\frac{n - c}{n} f_{c + 1} + i)}{1 - \frac{c}{n}} \\ = & \frac{(1 - p)^{L - 1} ((n - c) f_{c + 1} + n L) + \sum_{i = 1}^{L - 1} (1 - p)^{i - 1} p ((n - c) f_{c + 1} + n i)}{n - c} \end{aligned}$

然后有：

$\begin{aligned} (n - c) f_{c} = & f_{c + 1} ((1 - p)^{L - 1} (n - c)) \\ + & (1 - p)^{L - 1} n L \\ + & (n - c) p f_{c + 1} (\sum_{i = 1}^{L - 1} (1 - p)^{i - 1}) \\ + & n p (\sum_{i = 1}^{L - 1} (1 - p)^{i - 1} i) \end{aligned}$

然后有：

$\begin{aligned} (n - c) f_{c} = & f_{c + 1} ((1 - p)^{L - 1} (n - c)) \\ + & (1 - p)^{L - 1} n L \\ + & (n - c) f_{c + 1} (1 - (1 - p)^{L - 1}) \\ + & n p (\sum_{i = 1}^{L - 1} (1 - p)^{i - 1} i) \end{aligned}$

然后有：

$\begin{aligned} (n - c) f_{c} = & f_{c + 1} (n - c) \\ + & (1 - p)^{L - 1} n L \\ + & n p (\sum_{i = 1}^{L - 1} (1 - p)^{i - 1} i) \end{aligned}$

然后有：

$\begin{aligned} (n - c) f_{c} = & f_{c + 1} (n - c) \\ + & (1 - p)^{L - 1} n L \\ + & n p (\sum_{i = 0}^{L - 2} (1 - p)^{i} (i + 1)) \end{aligned}$

其中：

$\begin{aligned} S = \sum_{i = 0}^{L - 2} (1 - p)^{i} (i + 1) \\ \Rightarrow & (1 - p) S = \sum_{i = 1}^{L - 1} (1 - p)^{i} i \\ \Rightarrow & - p S = (1 - p)^{L - 1} (L - 1) - 1 - \sum_{i = 1}^{L - 2} (1 - p)^{i} \\ \Rightarrow & - p S = (1 - p)^{L - 1} (L - 1) - 1 - (\frac{1 - (1 - p)^{L - 1}}{p} - 1) \\ \Rightarrow & p S = \frac{1 - (1 - p)^{L - 1}}{p} - (1 - p)^{L - 1} (L - 1) \end{aligned}$

于是有：

$\begin{aligned} T = (1 - p)^{L - 1} n L + n (\frac{1 - (1 - p)^{L - 1}}{p} - (1 - p)^{L - 1} (L - 1)) \\ \Rightarrow & (n - c) f_{c} = (n - c) f_{c + 1} + T \\ \Rightarrow & f_{c} = f_{c + 1} + \frac{T}{(n - c)} \\ \Rightarrow & f_{0} = \sum_{i = 0}^{n - 1} \frac{T}{n - i} = T \sum_{i = 1}^{n} \frac{1}{i} \end{aligned}$

~~这么大数据范围的求逆元之和，出题人可能脑子出问题了~~

求逆元和的话，可以先每隔 $2 \times 10^{5}$ 打个表，然后查询就暴力扫一遍就行了

「codechef JULY19B MXMN」Maximum and Minimum

题目描述

大厨喜欢图论，为了表达他的热爱，他定义了函数 $f (G, x, y)$ ，其中 $G$ 为一个有边权的无向连通图， $x$ 和 $y$ 的图 $G$ 中的两个点

$f (G, x, y)$ 定义为 $G$ 中点 $x$ 和点 $y$ 之间的所有路径的权重的最小值，其中一条路径的权重定义为该路径上各边权的最大值

$C h e f$ 有两个连通图 $G_{1}$ 和 $G_{2}$

他们各有 $N$ 个顶点（编号为 $1$ 到 $N$ ）和 $M$ 条边

请你计算 $S = \sum_{i = 1}^{N - 1} \sum_{j = i + 1}^{N} f (g_{1}, i, j) \times f (G_{2}, i, j)$

答案对 $998244353$ 取模的结果

其中 $1 \leq N \leq 10^{5}, M = 2 N, 1 \leq u, v \leq N, 1 l e w \leq 10^{8}$ ，保证 $G_{1}, G_{2}$ 是连通图

社论

~~强行学了一波边分树合并~~

$k r u s k a l$ 重构树后，贡献成了： $d i s_{1} (i, j) \times d i s_{2} (i, j)$ ，枚举第二棵树的 $l c a$ ，考虑合并

考虑边分树合并，较浅的是左侧，较深的是右侧

因此对于左侧点，求一个到分治边的 $l c a$ 的权即可

这样合并的贡献就是左子树求和了，记得要乘以右子树大小

真社论：

模数是 $998244353$ （就我一个用了一大堆头文件然后忘记改模数的……）
实际上 $k r u s k a l$ 重构树本身就是三度化的……并不需要三度化（偷懒好啊）……
struct 的函数内部 static 好像是只有一个的……
lambda 表达式的坏处就是，如果 -f 了的话，根本不知道是哪里写挂了……
用 vector 有个好处就是，你知道你那里数组没开够……

henry_y 的函数

题目描述

某一天，你发现了一个神奇的函数 $g (x)$ ，它满足很多神奇的性质：

$g (1) = 1$
$g (p^{c}) = p \oplus c$ （ $p$ 为质数， $\oplus$ 表示异或）
$g (a b) = g (a) g (b)$ （ $a$ 与 $b$ 互质）

设：

$f (n) = (\sum_{i = 1}^{n} {⌊ \frac{n}{i} ⌋}^{2} g (i)) mod 998244353$

求出 $(f (1) \oplus f (2) \oplus \dots \oplus f (n)) mod 998244353$ 的值，其中 $1 \leq n \leq 10^{7}$

社论

这题妙啊……
$f (n) = \sum_{i = 1}^{n} {⌊ \frac{n}{i} ⌋}^{2} g (i)$

考虑一下 $f (n - 1)$ 和 $f (n)$ 有什么不同

~~发现只有 $d | n$ 的贡献会发生改变，因为 $gcd (n, n - 1) = 1$ ，于是非平凡因子不交~~

换句话说，考虑一下如果 $d | (n - 1)$ ，则 $⌊ \frac{n}{d} ⌋ = \frac{n - 1}{d} + ⌊ \frac{1}{d} ⌋ = \frac{n - 1}{d} + [d = 1]$ ，那么它会变化，当且仅当 $d = 1$

如果 $d ∤ (n - 1)$ ，则 $⌊ \frac{n}{d} ⌋ = d^{'} + ⌊ \frac{((n - 1) mod d) + 1}{d} ⌋$ ，那么它会改变，当且仅当 $(n - 1) mod d = d - 1$ ，即 $n - 1 = k d + (d - 1) \Rightarrow n = (k + 1) d$

综上，发生变化当且仅当 $d | n$ ，因此只有 $d | n$ 才会对 $f (n)$ 产生不同于 $f (n - 1)$ 的影响

那么变化量就很好计算了，它是一个狄利克雷卷积的形式（因为只需要枚举 $d | n$ ）

对于变化量，有：

$Δ_{f} (n) = \sum_{d | n} ({⌊ \frac{n}{d} ⌋}^{2} g (d) - {⌊ \frac{n - 1}{d} ⌋}^{2} g (d))$

由于 $d | n$ ，所以第一个下取整可以去掉，同时可以得知第二个下取整后就是 $\frac{n}{d} - 1$

既然没了下取整，就可以把 $d$ 和 $\frac{n}{d}$ 换一下了，即：

$\begin{aligned} Δ_{f} (n) = & \sum_{d | n} g (\frac{n}{d}) (d^{2} - (d - 1)^{2}) = & \sum_{d | n} g (\frac{n}{d}) (2 d - 1) = & (2 \sum_{d | n} g (d) \frac{n}{d}) - (\sum_{d | n} g (d)) \end{aligned}$

线性筛一下就好了

$g_{1} (p) = g (1) p + g (p) 1 = p + (p \oplus 1)$

$g_{1} (p^{c}) = \sum_{i = 0}^{c} g (p^{i}) p^{^{c - i}} = \sum_{i = 0}^{c} (p \oplus i) p^{c - i} = p \cdot g_{1} (p^{c - 1}) + (p \oplus c)$

$g_{2} (p) = g (1) + g (p) = 1 + (p \oplus 1)$

$g_{2} (p^{c}) = \sum_{i = 0}^{c} g (p^{i}) = \sum_{i = 0}^{c} (p \oplus i) = g_{2} (p^{c - 1}) + (p \oplus c)$

梦中的数论

题目描述

求：

$\sum_{i = 1}^{n} \sum_{j = 1}^{n} \sum_{k = 1}^{n} [(j ∣ i) \land ((j + k) ∣ i)]$

其中， $(j ∣ i) \land ((j + k) ∣ i)$ 指 $j$ 整除 $i$ 并且 $j + k$ 也整除 $i$

答案模 $998244353$ ，保证 $1 \leq n \leq 10^{10}$

社论

考虑后面那个是啥，相当于从 $i$ 的约数中选了两个不相同的，求方案数

于是答案就是：

$\sum_{i = 1}^{n} (\binom{σ_{0} (i)}{2}) = \sum_{i = 1}^{n} \frac{σ_{0} (i)^{2} - σ_{0} (i)}{2}$

对于 $\sum σ_{0} (i)$ ，可以数论分块的 $O (\sqrt{n})$ 求，对于 $\sum σ_{0}^{2} (i)$ ，就直接 $min_25$ 筛就好了

Check,Check,Check one two!

题目描述

给定字符串 $S$ ，以及 $k_{1}, k_{2}$ ，求：

$\sum_{1 \leq i < j \leq n} lcp (i, j) \times lcs (i, j) \times [lcp (i, j) \leq k_{1}] \times [lcs (i, j) \leq k_{2}]$

其中：

$lcp (i, j)$ 表示从字符串第 $i$ 个位置开始的后缀和从第 $j$ 个位置开始的后缀的最长公共前缀长度
$lcs (i, j)$ 表示在字符串第 $i$ 个位置结束的前缀和在第 $j$ 个位置结束的前缀的最长公共后缀长度

社论

先不考虑神仙的 $S A$ 做法，考虑暴力

题意转化为了，给定两棵树，求两两点对的 $l c a$ 处的权值的乘积的和

边分树合并一下就好了

共价大爷游长沙

题目描述

有一棵 $n$ 个节点的树， $m$ 次操作，有四种操作

删除一条边并加入一条边，保证操作之后还是一棵树
在路径集合 $S$ 中加入一条路径 $(x, y)$
删除路径集合 $S$ 中的一条路径。
对于一条边 $(x, y)$ （保证存在），询问是否 $S$ 中的所有路径都经过了这条边

其中 $n, m \leq 300000$

社论

考虑对每个 $(x, y)$ 打上一个随机权值，那么一条边合法，当且仅当它的一个子树中的边权异或和等于所有加入的随机权值的异或和

「NOI2014」魔法森林

题目描述

给定一张无向图，每条边有两个权值 $A_{i}, B_{i}$

要求找出一条从 $1$ 号点到 $n$ 号点的路径，使得所有经过了的边 $i$ ，最小化 $max_{i} (A_{i}) + max_{i} (B_{i})$ 最小，求这个最小值

其中 $n \leq 10^{5}$

社论

先把边按照 $B$ 从小到大排序，然后就可以依次枚举了，这样就只有一个维度 $A$ 的限制了

不难发现它就是最小生成树，直接 $L C T$ 维护就好了

一个不正经的做法：动态加边最短路，然而官方数据没卡……