【题解】牛客练习赛 68 题解

A

注意条件 且 互不相同，所以一个区间内最小未出现的自然数就等于不在这个区间内最小出现的自然数。预处理前缀后缀最小值就好了。
代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44866335

B

发现当 时答案必为 0。

于是我们只需要预处理 n < 199999 的答案就好了。可以推式子或者前缀和处理。
代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44866341

C

我们考虑单组询问 L 怎么做：实际上就是把所有 的所有边都加进去 询问互相可达点对，可以用并查集维护。

那么多组询问就可以都离线下来，把询问和边放在一起排序然后处理就好了。

其实在线也可以做：处理处加入每条边后的答案，询问的时候只需要找到最后一个 的边，拿加入这个边后的答案作为这次询问的答案就行了。
代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44866360

D

首先我们发现每个位置本质是一样的，所以如果我们想求第 i 个位置开始的粉丝经过 T 时间到达第 j 个位置的粉丝的期望人数可以整体平移到起点为 0 的情况，所以我们只需要处理起点为 0 的情况就好了。

考虑暴力：设 表示在 i 时刻一个粉丝从 0 位置开始在 j 位置的概率。

转移是

直接暴力矩阵乘法转移是 的，应该是过不了的。

E

考虑一个暴力的 dp：设 表示考虑了前 i 个最多能被划为多少段，转移时枚举从 转移而来 需要保证 [j+1,i] 不是回文串。

我们修改转移的限制：我们只需要要求 [j+1,i] 能被划分成回文串就可以了，不难发现在最优性的限制下答案不会改变。

那么我们考虑有哪些串不能被划分呢？实际上很少：
1. aaaaaaaaa
2. ababababa
3. aaaabaaaa

简要证明：
首先如果本身不是回文串 不需要划分，所以我们只需要考虑回文串的情况：
首先我们证明对于 一定能被划分：我们从左往右找到第一个位置 i，满足 [1,i] 中 i 位置的字母第一次出现。将其划分为 [1,i] 和 [i+1,n] 即符合题意。
接下来我们发现 并且不属于三种情况的一定满足以下条件：

1. 长度为偶数
2. s[n/2]=s[n/2+1]

我们考虑在 n/2-1 处划分 即可满足题意。

于是我们考虑修正后的状态如何转移：
1. 能转移过来的状态是一个前缀 预处理前缀 max 即可
2. 是和奇偶性有关的一个前缀 分奇偶性维护前缀 max
3. 显然只有一个 这个需要注意 他可能会混入 2 情况的转移 所以我们还需要维护次 max 和它们的位置

时间复杂度 O(n)
代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44866372

F

我们定义 ，实际上是要求。 。考虑设 。

我们如果能求出一个 （除法定义为狄利克雷卷积逆），显然 F,G,H 都是积性函数。可以发现



然后我们观察一些性质：我们发现如果代入 F(p) 可以得到：



所以发现对于一个 x ，设 ，如果 ，那么 H(x) = 0。

那么 H(x) 不为 0 的部分有多少呢？我们可以考虑所有满足 的地方的 x 一定可以表示成 的形式：

>证明：因为任何一个 的数都能被写成 2x+3y 的形式（根据裴蜀定理）

所以这样的数的个数有：



所以我们只需要爆搜出所有这样的数，然后拉格朗日插值快速算一下 G 的前缀和就好了。（实际操作的时候可以预处理 的 G 的前缀和来加速。

如果我们对于 的查询 G 前缀和的部分预处理， 的部分插值，程序实测只用插 2026 个值。

大概估计一下复杂度：首先拉格朗日插值对于一个 H 有值的地方 x，查询的是 。

那么首先如果一个数如果对插值复杂度有贡献，要满足 ，所以插值部分的复杂度就是 了。总复杂度 。
代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44866385