题解 | solution for all

很抱歉带给了大家不好的体验。C是很典的原，D假了。这场应该会 unrated。

A:输出 $n-1,1$ 即可。

B:将 $b_i$ 减去 $k$ ，对于非正整数 $b_i$ 将其对应的 $a_i$ 直接贡献到答案内，非正整数 $b_i$ 的绝对值之和记为 $s$ 。对于剩下的对，问题即转化为 01 背包问题。时间复杂度 $O(n^2w)$ 。

C:这道题与树上独立集计数等价。设 $dp_{u,0/1}$ 表示点 $u$ 是否与树外点有连边时的子树连边方案数。转移如下

dp_{u,0}=\prod_{v\in son_u}(dp_{v,0} dp_{v,1})\\ dp_{u,1}=\prod_{v\in son_u}dp_{v,0}

$O(n)$ 即可。

D:题目假了，想的是并查集+trie。但是实际上我们考虑题目的表述为存在性表述。我们将任意两个相似的歌曲连一条边，可以发现题目要求的实际上是 $\text{大小为 1 的连通块个数} 1$ 与 $n$ 的较小值。

实际上需要将题目的 $f$ 限制进行一定的转化。

我们对每个位置 $x$ 分别考虑其 $f$ 值是否满足题目要求。

当 $f(x)=x$ 时，明显两个条件都满足。
假设有两个位置 $x,y$ ，当 $f(x)=y,f(y)=x$ 时，可以满足第二个条件。假设 $x<y$ ，则需要满足 $y=x 1$ 或 $y=x 2$ 。

因此我们可以设一个序列 $v_i$ 表示第 $i$ 个点是否被确定，被确定则设为 $1$ ，否则设为 $0$ 。我们只有当 $x$ 找到了与其匹配的 $y$ 后才将 $x$ 标记为 $1$ 。由上面的分析可得，我们只需要考虑 $v$ 其中的连续三个点的转移。

但我们又注意到：

000 是明显不合法的，因为第一个 0 不可能再找到与其匹配的位置。

同样的，第一位数为0的都不合法。

所以实际上我们只需要考虑连续两个点的转移，确定当前数是否与前面的数进行匹配，还是留空，如下：

00 -> 101 -> 01
01 -> 111 -> 11
10 -> 100 -> 00
10 -> 101 -> 01
10 -> 111 -> 11
11 -> 110 -> 10
11 -> 111 -> 11

因此我们答案可用矩阵快速幂计算得到。

对于不同的 $k$ 都有不同的矩阵。时间复杂度为 $O(8^k \log n)$ 。

考虑预处理出每个矩阵的 2 的幂次的位置，即 $A,A^2,A^{2^2},A^{2^3},\dots,A^{2^{60}}$ 。这个 trick 可见 NOI2020d1A。

时间复杂度优化为 $O(8^k \log n T\cdot 4^k \log n)$ 。

令 $d=\gcd(i,j),x=\frac{i}{d},y=\frac{j}{d}$

则 $\gcd(x,y)=1$

$ij=k(i-j)\implies xyd=k(x-y)$

$\because \gcd(xy,x-y)=1,\gcd(d,k)=1$

$\therefore d=x-y,k=xy$

因此题目所求即可转化为

\sum_{d=1}^{n} \sum_{y=1}^{\lfloor \frac{n}{d}\rfloor -d} [\gcd(y,d)=1][y(y d) \le n]

经过莫比乌斯反演，即有

\sum_{g=1}^{n}\mu(g)\sum_{g \mid y}^{n} \sum_{g \mid d} [y \le \lfloor \frac{n}{d}\rfloor -d][y(y d) \le n]

再次化简，可以得到

\sum_{g=1}^{n}\mu(g)\sum_{y=1}^{\lfloor \frac{n}{g}\rfloor}\sum_{d=1}^{\lfloor \frac{n}{g}\rfloor}[yg \le \lfloor \frac{n}{dg}\rfloor-dg][y(y d)\le \lfloor \frac{n}{g^2}\rfloor]

对两个中括号内分别化简，可以得到

dy d^2 \le \lfloor \frac{n}{g^2}\rfloor\\ dy y^2 \le \lfloor \frac{n}{g^2}\rfloor

因此原式可化为

\sum_{g=1}^{n}\mu(g)\sum_{y=1}^{\lfloor \frac{n}{g}\rfloor}\sum_{d=1}^{\lfloor \frac{n}{g}\rfloor}[dy \max(d,y)^2 \le \lfloor \frac{n}{g^2}\rfloor]

不妨假定 $d<y$ ，又特殊考虑 $d=y$ 的情况，则有

\displaystyle \sum_{g=1}^{n}\mu(g)\left(\left\lfloor \sqrt{\frac{n}{2g^2}}\right\rfloor 2\sum_{y=1}^{\left\lfloor \sqrt{\frac{n}{g^2}}\right\rfloor}\min\left(y-1,\max\left(\left\lfloor \frac{n}{g^2y}\right\rfloor-y,0 \right)\right) \right)

我们求解

y-1 <\left\lfloor \frac{n}{g^2y}\right\rfloor-y

可以得到

y\le \left\lfloor \sqrt{\frac{n}{2g^2}}\right\rfloor

记 $d=\left\lfloor \sqrt{\frac{n}{2g^2}}\right\rfloor,t=\left\lfloor \sqrt{\frac{n}{g^2}}\right\rfloor$ ，则式子可简写为

\sum_{g=1}^{\lfloor \sqrt{n} \rfloor} \mu(g)\left(d d(d 1)-2d \right) 2\sum_{g=1}^{n} \mu(g)\sum_{y=d 1}^{t} \max\left(\left\lfloor \frac{n}{g^2y}\right\rfloor-y,0 \right)

注意到仅当 $y \le \sqrt{\frac{n}{g^2}}$ 时 $\left\lfloor \frac{n}{g^2y}\right\rfloor-y>0$ ，因此有答案为

\sum_{g=1}^{\lfloor \sqrt{n} \rfloor} \mu(g)d^2 2\sum_{g=1}^{\lfloor \sqrt{n} \rfloor} \mu(g)\sum_{y=d 1}^{t} \left(\left\lfloor \frac{n}{g^2y}\right\rfloor-y \right)

总时间复杂度为 $O(\sqrt{n}\ln \sqrt{n})$ 。