牛客练习赛77官方题解

T1
签到题，等差数列求和O(1)输出即可

T2
类似的思路，我们发现约数的条件我们也是可以转化成倍数的
这样就是考虑x的倍数在n之内的数的求和，我们同样可以用等差数列求和来求出来

T3
容易发现我们的这个函数G(n)=sum i=1..n i*n/i
这个很好想我们只需要知道每个i出现在约数有多少个倍数满足这个条件，因此还是转化成倍数问题
于是这个我们其实可以用整除分块来优化
推荐一个博客：https://www.cnblogs.com/peng-ym/p/8661118.html

T4
本题我们用一种折半思想类似折半的思想来做
相当于我们枚举一位，然后另外一位用meeting in the middle做
但是我们还需要减掉一些重复的情况，这个很好推导具体可以见代码
于是我们发现这样我们就可以hash了
但是这题我们的unorderedmap过不了，因此需要手写哈希。
时空复杂度：O(N*30)
注意hash的复杂度是O(1)的

T5
容易发现我们暴力N^2建图跑割点正确性是对的
因此我们下一步目标是如何优化建图
显然，这道题 tarjan 算法是必须使用的。
tarjan 算法的复杂度就是图的大小。
我们发现可以在值域下手
于是我们发现这个gcd和其他约数没有关系，我们只需要考虑质数
显然这个范围是可以接受的
因此我们每次像质因数连边，然后在无向图上缩点，判断强联通分量就可以了
这样我们只需要对每个点的出边考虑就可以了
但是我们需要注意的是要判断一下单独一个点的情况，很多人好像都WA在这里了
容易发现我们建图后的规模是可以接受的
时间复杂度O(Nsqrt(N))或者O(N log N)

T6
我们首先发现正着不好做，考虑到“不超过 $m$ ”这个限制太强了，我们把它容斥掉。首先长度不超过 $m$ 等价于没有长度为 $m+1$ 的，然后变成枚举位置 $i_1, i_2, \ldots, i_k$ 使得 $a_{i_j}, a_{i_j+1}, \ldots, a_{i_j+m}$ 满足条件。
然后我们可以分类讨论：
于是就是公差为 $\pm1$ 的等差连续子序列。考虑两段限制区间叠在一起的情况，如果严格重合，那么显然公差相同；如果只有端点重合，由于这是一个排列，公差也只能相同。合并限制区间，让它们任意两个都不重合。

在这种情况下，设限制区间有 $x$ 个，不在限制区间里的有 $y$ 个，那么先把所有限制区间各看作一个数，排列所有数的相对大小，有 $(x+y)!$ 种情况；再考虑限制区间的公差，有 $2^x$ 种情况。

因此我们记 $f(i, j, k)$ 表示把前 $i$ 个点分成 $j$ 个限制区间和 $k-j$ 个无限制点的容斥系数和， $g(i, j, k)$ 表示在上述条件下 $i$ 作为限制区间末尾的容斥系数和。

初值$ $f(0, 0, 0)=g(0, 0, 0)=1$ $

转移$ $\begin{align}g(i, j, k) & =-\sum_{p=i-m}^{i-1}g(p, j, k)-f(i-m-1, j-1, k-1) \\ f(i, j, k) & =g(i, j, k)+f(i-1, j, k-1)\end{align}$ $

答案$ $\sum_{j=0}^n\sum_{k=0}^n f(n, j, k) \cdot 2^j \cdot k!$ $

注意到在上述转移式中 $j$ 的需求不高。设

$\begin{align}F(i, k)&=\sum_{j=0}^n f(i, j, k) \cdot 2^j \\ G(i, k)&=\sum_{j=0}^ng(i, j, k) \cdot 2^j\end{align}$

不难改写上述动态规划为：

初值$ $F(0, 0)=G(0, 0)=1$ $

转移$ $\begin{align}G(i, k) & =-\sum_{p=i-m}^{i-1}G(p, k)-2F(i-m-1, k-1) \\ F(i, k) & =G(i, k)+F(i-1, k-1)\end{align}$ $

答案$ $\sum_{k=0}^nF(n, k) \cdot k!$ $

可以采用前缀和优化后时间复杂度 $O(n^2),$ 滚动数组优化后空间复杂度 $O(n)$ .