2019.11 月赛题解

Xiejiadong edited 4 年，2 月前

前排广告位

花絮

题目背景是真的

#	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, \dots, k - 1$ 编号的话，可以发现，题目转换成了 $k$ 进制的转换问题。

根据给出的 $x$ ，从后往前依次确定每一位的大小。

Comments

Xiejiadong ：如果转换成了进制转换的模型，根本不会出线乘法运算，所以也不可能会出现爆 long long 之类的问题。

Problem B

First Solved：emengdeath

首先可以发现的是 $k$ 很大是毫无意义的事情。

设 $| s |$ 表示字符集大小，当 $k \geq | s | - 1$ 的时候，肯定是所有的字符串都能等价了。

首先我们考虑等价类的划分问题。

如果我们认为相同的字母都属于同一个容器的话，那么相当于把最多 $8$ 个字母放入若干个相同的容器中，可以发现这是第二类斯特林数的模型。

我们知道 $S (8, x) (0 \leq x \leq 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$ 和 $2 n$ 不能同时取”的约束，答案记为 $f (n, r, s)$ 。

将 $[2 n]$ 分为 $n$ 对，分别是 $(1, 2), (3, 4), \dots, (2 n - 1, 2 n)$ ，易知对于任意对 $(2 k - 1, 2 k)$ ，有三种可能的情况：

奇对。选 $2 k - 1$ ，不选 $2 k$ 。
偶对。选 $2 k$ ，不选 $2 k - 1$ 。
空对。 $2 k$ 和 $2 k - 1$ 都不选。

因为禁止相邻对，所以禁止一个偶对后面紧跟着一个奇对。已知有 $r$ 个奇对和 $s$ 个偶对，则有 $n - r - s$ 个空对，这些空对把长度为 $n$ 的对串分成了 $n - r - s + 1$ 段，每段内部只有奇对和偶对（可能为空）。考虑每段内部，由于禁止一个偶对后面紧跟着一个奇对，排列方式一定是所有的奇对在左边，所有的偶对在右边，有用的信息只有奇偶对的个数。至此可以做一个集合到方程组解的一一映射，其中 $x_{i} \geq 0$ 表示第 $i$ 段的奇对数， $y_{i} \geq 0$ 表示第 $i$ 段的偶对数，方程组如下：
$$
\left{
$\begin{matrix} x_{1} + x_{2} + \dots + x_{n - r - s + 1} = r \\ y_{1} + y_{2} + \dots + y_{n - r - s + 1} = s \end{matrix}$
\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$ 和 $2 n$ ，这部分其实就是 $f (n - 2, r - 1, s - 1)$ ，故
$\begin{aligned} 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{r s}{(n - r) (n - s)}) (\binom{n - r}{s}) (\binom{n - s}{r}) \\ = \frac{n^{2} - s n - r n}{(n - r) (n - s)} (\binom{n - r}{s}) (\binom{n - s}{r}) \end{aligned}$
Double counting，从两个方向数有序对 $(A, E)$ 的数量，其中 $A$ 是一种子集取法，遍历 $g (n, r, s)$ 的所有解， $E$ 是 $A$ 中空对的编号，共有 $n - s - r$ 个可能的取值，考虑先枚举 $A$ 还是先枚举 $E$ ，可得
$\begin{aligned} (n - s - r) g (n, s, r) = n f (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} - s n - r n}{(n - r) (n - s)} (\binom{n - r}{s}) (\binom{n - s}{r}) \end{aligned}$
注意特判边界情况。

Comments

Grunt ：本题出自笔者修的一门组合数学课的课后作业，感觉这个问题和做法都很有意思，就稍微加强了下，搬运过来。

Problem D

First Solved：ldxxx

比较简单的多项式运算。

假设特殊点的权值分别是 $a_{1}, a_{2}, \cdot a_{k}$ ，非特殊点的权值分别是 $b_{1}, b_{2}, \dots b_{m}$ ，显然 $k + m = n$ 。

我们把边氛围分为三类：

特殊点与特殊点之间的边，需要计算边权；
特殊点与非特殊点之间的边，需要计算边权；
非特殊点与非特殊点之间的边，不需要计算边权。

于是我们可以通过总的边权减去非特殊点之间的边权得到。

总的边权

$\begin{aligned} a_{1} a_{2} + a_{1} a_{3} + \dots + a_{1} a_{k} + a_{1} b_{1} + \dots a_{1} b_{m} + \dots \\ = & \frac{1}{2} [(a_{1} + \dots + a_{k} + b_{1} + \dots + b_{m}) \times (a_{1} + \dots + a_{k} + b_{1} + \dots + b_{m}) - (a_{1}^{2} + \dots a_{k}^{2} + b_{1}^{2} + \dots + b_{m}^{2})] \end{aligned}$

于是，通过计算所有点权的和以及平方和就可以得到总的边权。

非特殊点与非特殊点之间的边的边权

与上面类似

$b_{1} b_{2} + b_{1} b_{3} + \dots + b_{1} b_{m} + b_{2} b_{3} \dots = \frac{1}{2} [(b_{1} + b_{2} + \dots + b_{m}) \times (b_{1} + b_{2} + \dots + b_{m}) - (b_{1}^{2} + \dots + b_{m})]$

剩下的问题就是计算原本环上存在边的边权。直接枚举环上的每一条边是否属于非特殊点与非特殊点之间的边，如果是则加上这条边的边权，否则已经存在则不再做计算。

Problem E

First Solved：poorwill

先考虑莫比乌斯反演

$F (x) = \sum_{a_{1}} \dots \sum_{a_{k}} [(a_{1}, \dots, a_{k}, n) == x]$

$G (x) = \sum_{x | d} F (x) = {\begin{cases} (\frac{n}{x})^{k} & x | d \\ 0 & o t h e r w i s e \end{cases}$

我们要求的 $\sum_{i = 1}^{n} H (i)$ 有

$H (n) = F (1, n) = \sum_{d | n} μ (d) (\frac{n}{d})^{k} = μ * n^{k}$

$\sum_{i = 1}^{n} H (i) = \sum_{i = 1}^{n} \sum_{d | i} μ (d) (\frac{i}{d})^{k} = \sum_{d = 1}^{n} μ (d) \sum_{i = 1}^{n / d} i^{k}$

幂方和可以用伯努利数预处理 $O (k^{2})$ ，然后 $O (k)$ 求值。

其余用上数论分块和杜教筛求 $μ$ 。

复杂度 $O (n^{\frac{2}{3}} + k \sqrt{n})$ 。

Comments

Weaver_zhu ：很没意思的一道题，和多校的一道题套路也重的比较多。

Xiejiadong ：两个月前的月赛囤下来的题目。由于没有什么好的 idea 所以就放上来了。

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

17 0

interestingLSY

5 年，4 月前

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

回复 1 0

Xiejiadong

5 年，4 月前

蟹蟹支持刘队nb

回复 1 0

卡题卡常卡精度

5 年，4 月前

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

回复 0 0

kimoyami

5 年，4 月前

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

回复 3 0

interestingLSY

5 年，4 月前

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

回复 2 0

interestingLSY

5 年，4 月前

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

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

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

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

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

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

回复 2 0

前排广告位

花絮

Problem A

First Solved：gyz_gyz

Comments

Problem B

First Solved：emengdeath

Comments

Problem C

First Solved：DeaphetS

Comments

Problem D

First Solved：ldxxx

Problem E

First Solved：poorwill

Comments

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

Comments

服务

开源

关于我们