好题，为良心出题银点赞！
2019.11 月赛题解
Xiejiadong edited 3 年，10 月前
前排广告位
花絮
- 题目背景是真的
| # | Tag | Idea | Developer | Tester |
|---|---|---|---|---|
| A | 模拟 | Xiejiadong | Xiejiadong | 10185101232 Grunt |
| B | 数学 暴力 哈希 | Xiejiadong | Xiejiadong | 10185101232 Grunt |
| C | 组合数学 | Grunt | Grunt | 10185101232 Xiejiadong |
| D | 简单多项式计算 | Xiejiadong | Xiejiadong | 10185101232 Grunt |
| E | 筛法 | Weaver_zhu | Weaver_zhu | 10185101232 |
Problem A
First Solved：gyz_gyz
签到题。
特意固定了 $k$ 的大小，也就是每一位可供选择的字符数量相同。
如果按照字典序的顺序对每一个字母进行 $0,1,\cdots ,k-1$ 编号的话 ，可以发现，题目转换成了 $k$ 进制的转换问题。
根据给出的 $x$ ，从后往前依次确定每一位的大小。
Comments
Xiejiadong ：如果转换成了进制转换的模型，根本不会出线乘法运算，所以也不可能会出现爆 long long 之类的问题。
Problem B
First Solved：emengdeath
首先可以发现的是 $k$ 很大是毫无意义的事情。
- 设 $|s|$ 表示字符集大小，当 $k\ge |s|-1 $ 的时候，肯定是所有的字符串都能等价了。
首先我们考虑等价类的划分问题。
如果我们认为相同的字母都属于同一个容器的话，那么相当于把最多 $8$ 个字母放入若干个相同的容器中，可以发现这是第二类斯特林数的模型。
我们知道 $S(8,x)(0\le x\le 8)$ 最大是 $S(8,4)=1701$ 。
也就是说，等价类划分的关系，最多只有 $1701$ 种情况，于是可以考虑枚举所有的等价类划分的情况。
对于已经确定的等价类划分，我们现在需要做的无非就是判断有多少个字符串是等价的。
这部分可以通过字符串 Hash 来实现，直接暴力的字符串 Hash 需要每一次重新计算每一个字符串对应的 Hash 值，是无法通过这道题的。
因为这里最多只有 $8$ 个字母，我们可以考虑预处理每一个字符串中每一个字母所在的位置对应的 Hash 值。
因为每一次都是不同字母之间的全部替换，所以这样每一次计算每一个字符串 Hash 的代价变成了 $O(8)$ ，就可以卡通过此题了。
Comments
Xiejiadong ：一开始的 idea 是想做所有字母映射的等价。想了很久发现自己不会做。后来发现字母集改小就可以做了，而且似乎思路挺妙的。
oxx1108 ： 感觉这个得和出题人心灵相通才能做吧。
Xiejiadong ：那我时限放宽一些，看看有没有各种不同的方法卡过去。
Problem C
First Solved：DeaphetS
链的版本
注意到题面要求的其实是一个”环的版本”，正常想法是先给出“链的版本”的做法，即去掉“$1$ 和 $2n$ 不能同时取”的约束，答案记为 $f(n,r,s)$。
将 $[2n]$ 分为 $n$ 对，分别是 $(1,2),(3,4),\cdots,(2n-1,2n)$，易知对于任意对 $(2k-1,2k)$，有三种可能的情况：
- 奇对。选 $2k-1$，不选 $2k$。
- 偶对。选 $2k$，不选 $2k-1$。
- 空对。$2k$ 和 $2k-1$ 都不选。
因为禁止相邻对，所以禁止一个偶对后面紧跟着一个奇对。已知有 $r$ 个奇对和 $s$ 个偶对，则有 $n-r-s$ 个空对，这些空对把长度为 $n$ 的对串分成了 $n-r-s+1$ 段，每段内部只有奇对和偶对（可能为空）。考虑每段内部，由于禁止一个偶对后面紧跟着一个奇对，排列方式一定是所有的奇对在左边，所有的偶对在右边，有用的信息只有奇偶对的个数。至此可以做一个集合到方程组解的一一映射，其中 $x_i\ge0$ 表示第 $i$ 段的奇对数，$y_i\ge0$ 表示第 $i$ 段的偶对数，方程组如下：
$$
\left{
\begin{array}{c}
x_1+x_2+\cdots+x_{n-r-s+1}=r\\
y_1+y_2+\cdots+y_{n-r-s+1}=s
\end{array}
\right.
$$
显然两个方程是独立的，$f(n,r,s)= \binom{n-r}{s}\binom{n-s}{r}$。
环的版本
记环的版本的答案为 $g(n,r,s)$，给出两种不同的解法。
容斥，显然 $f(n,r,s)>g(n,r,s)$，$f(n,r,s)$ 多出的部分是恰巧同时选了 $1$ 和 $2n$，这部分其实就是 $f(n-2,r-1,s-1)$，故
$$
\begin{align}
g(n,r,s)
&=f(n,r,s)-f(n-2,r-1,s-1)\\
&=\binom{n-r}{s}\binom{n-s}{r}-\binom{n-r-1}{s-1}\binom{n-s-1}{r-1}\\
&=(1+\frac{rs}{(n-r)(n-s)})\binom{n-r}{s}\binom{n-s}{r}\\
&=\frac{n^2-sn-rn}{(n-r)(n-s)}\binom{n-r}{s}\binom{n-s}{r}
\end{align}
$$
Double counting，从两个方向数有序对 $(A,E)$ 的数量，其中 $A$ 是一种子集取法，遍历 $g(n,r,s)$ 的所有解，$E$ 是 $A$ 中空对的编号，共有 $n-s-r$ 个可能的取值，考虑先枚举 $A$ 还是先枚举 $E$，可得
$$
\begin{equation}\begin{split}
(n-s-r)g(n,s,r)=nf(n-1,s,r)\\
\Rightarrow g(n,s,r)=\frac{n}{n-s-r}\binom{n-r-1}{s}\binom{n-s-1}{r}\\
=\frac{n(n-s-r)(n-s-r)}{(n-s-r)(n-r)(n-s)}\binom{n-r}{s}\binom{n-s}{r}\\
=\frac{n^2-sn-rn}{(n-r)(n-s)}\binom{n-r}{s}\binom{n-s}{r}
\end{split}\end{equation}
$$
注意特判边界情况。
Comments
Grunt ：本题出自笔者修的一门组合数学课的课后作业，感觉这个问题和做法都很有意思，就稍微加强了下，搬运过来。
Problem D
First Solved：ldxxx
比较简单的多项式运算。
假设特殊点的权值分别是 $a_1,a_2,\cdot a_k$ ，非特殊点的权值分别是 $b_1,b_2,\cdots b_m$ ，显然 $k+m=n$ 。
我们把边氛围分为三类：
- 特殊点与特殊点之间的边，需要计算边权；
- 特殊点与非特殊点之间的边，需要计算边权；
- 非特殊点与非特殊点之间的边，不需要计算边权。
于是我们可以通过总的边权减去非特殊点之间的边权得到。
总的边权
$$
\begin{align}
& a_1a_2+a_1a_3+\cdots +a_1a_k+a_1b_1+\cdots a_1b_m+\cdots\\
=& \frac{1}{2}[(a_1+\cdots +a_k+b_1+\cdots +b_m)\times (a_1+\cdots +a_k+b_1+\cdots +b_m)-(a_1^2+\cdots a_k^2+b_1^2+\cdots +b_m^2)]
\end{align}
$$
于是，通过计算所有点权的和以及平方和就可以得到总的边权。
非特殊点与非特殊点之间的边的边权
与上面类似
$$b_1b_2+b_1b_3+\cdots +b_1b_m+b_2b_3\cdots \\
=\frac{1}{2}[(b_1+b_2+\cdots +b_m)\times (b_1+b_2+\cdots +b_m)-(b_1^2+\cdots + b_m)]$$
剩下的问题就是计算原本环上存在边的边权。直接枚举环上的每一条边是否属于非特殊点与非特殊点之间的边，如果是则加上这条边的边权，否则已经存在则不再做计算。
Problem E
First Solved：poorwill
先考虑莫比乌斯反演
$$F(x) = \sum\limits_{a_1}…\sum\limits_{a_k}[(a_1,…,a_k,n)==x]$$
$$
G(x)=\sum\limits_{x|d}F(x)=\begin{cases}
(\frac{n}{x})^{k} & x | d \\
0 & otherwise
\end{cases}$$
我们要求的 $\sum\limits_{i=1}^{n}H(i)$ 有
$$
H(n) =
F(1, n) = \sum\limits_{d|n}\mu(d) (\frac{n}{d})^{k} = \mu * n^k
$$
$$
\sum\limits_{i=1}^{n}H(i) = \sum\limits_{i=1}^{n}\sum\limits_{d|i}\mu(d)(\frac{i}{d})^k =\sum\limits_{d=1}^{n}\mu{(d)}\sum\limits_{i=1}^{n/d}i^k
$$
幂方和可以用伯努利数预处理 $O(k^2)$，然后 $O(k)$ 求值。
其余用上数论分块和杜教筛求 $\mu$ 。
复杂度 $O(n^{\frac{2}{3}} + k\sqrt{n})$ 。
Comments
Weaver_zhu ：很没意思的一道题，和多校的一道题套路也重的比较多。
Xiejiadong ：两个月前的月赛囤下来的题目。由于没有什么好的 idea 所以就放上来了。
蟹蟹支持 刘队nb