2019.11 月赛题解

Xiejiadong edited 10 月,4 周前

前排广告位

EOJ Monthly 招募贴

花絮

# 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$ 很大是毫无意义的事情。

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

如果我们认为相同的字母都属于同一个容器的话,那么相当于把最多 $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$,可得
$$
(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}
$$
注意特判边界情况。

Comments

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

Problem D

First Solved:ldxxx

比较简单的多项式运算。

假设特殊点的权值分别是 $a_1,a_2,\cdot a_k$ ,非特殊点的权值分别是 $b_1,b_2,\cdots b_m$ ,显然 $k+m=n$ 。

我们把边氛围分为三类:

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

总的边权

$$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)]$$

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

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

与上面类似

$$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

好题,为良心出题银点赞!

Xiejiadong

蟹蟹支持 刘队nb

卡题卡常卡精度

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

kimoyami

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

interestingLSY

(小声哔哔)是不是可以打表啊

interestingLSY

我的写法就是 BFS,从 ah 依次考虑,同时维护

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

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

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

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

无须去重(因为根本不会重复)

你当前正在回复 博客/题目
存在问题!