2019.11 月赛题解

Xiejiadong edited 3 年，9 月前

前排广告位

EOJ Monthly 招募贴

花絮

• 题目背景是真的

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)$，有三种可能的情况：

1. 奇对。选 $2k-1$，不选 $2k$。
2. 偶对。选 $2k$，不选 $2k-1$。
3. 空对。$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 所以就放上来了。

恭喜 DeaphetS ， emengdeath ， interestingLSY 分别获得冠亚季军。

Comments

interestingLSY

4 年，11 月前

好题，为良心出题银点赞！

回复 1 0

Xiejiadong

4 年，11 月前

蟹蟹支持 刘队nb

回复 1 0

卡题卡常卡精度

4 年，11 月前

请问怎么枚举等价类划分啊蒟蒻不会写……

回复 0 0

kimoyami

4 年，11 月前

预处理暴力跑出所有情况，然后判断那些是等价类，去重吧

回复 3 0

interestingLSY

4 年，11 月前

（小声哔哔）是不是可以打表啊

回复 2 0

interestingLSY

4 年，11 月前

我的写法就是 BFS，从 a 到 h 依次考虑，同时维护

• 总共有几个等价类
• 每个等价类中都有啥

每次新加入一个字母的时候，有两种情况

• 新开一个等价类
• 将这个字母加入到之前的某一个等价类中

与第二类斯特林数的递推思想类似

无须去重（因为根本不会重复）

回复 2 0