2019.11 月赛题解

Xiejiadong edited 1 月,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

签到题。

特意固定了 的大小,也就是每一位可供选择的字符数量相同。

如果按照字典序的顺序对每一个字母进行 编号的话 ,可以发现,题目转换成了 进制的转换问题。

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

Comments

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

Problem B

First Solved:emengdeath

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

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

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

我们知道 最大是

也就是说,等价类划分的关系,最多只有 种情况,于是可以考虑枚举所有的等价类划分的情况。

对于已经确定的等价类划分,我们现在需要做的无非就是判断有多少个字符串是等价的。

这部分可以通过字符串 Hash 来实现,直接暴力的字符串 Hash 需要每一次重新计算每一个字符串对应的 Hash 值,是无法通过这道题的。

因为这里最多只有 个字母,我们可以考虑预处理每一个字符串中每一个字母所在的位置对应的 Hash 值。

因为每一次都是不同字母之间的全部替换,所以这样每一次计算每一个字符串 Hash 的代价变成了 ,就可以卡通过此题了。

Comments

Xiejiadong :一开始的 idea 是想做所有字母映射的等价。想了很久发现自己不会做。后来发现字母集改小就可以做了,而且似乎思路挺妙的。

oxx1108 : 感觉这个得和出题人心灵相通才能做吧。

Xiejiadong :那我时限放宽一些,看看有没有各种不同的方法卡过去。

Problem C

First Solved:DeaphetS

链的版本

注意到题面要求的其实是一个”环的版本”,正常想法是先给出“链的版本”的做法,即去掉“ 不能同时取”的约束,答案记为

分为 对,分别是 ,易知对于任意对 ,有三种可能的情况:

  1. 奇对。选 ,不选
  2. 偶对。选 ,不选
  3. 空对。 都不选。

因为禁止相邻对,所以禁止一个偶对后面紧跟着一个奇对。已知有 个奇对和 个偶对,则有 个空对,这些空对把长度为 的对串分成了 段,每段内部只有奇对和偶对(可能为空)。考虑每段内部,由于禁止一个偶对后面紧跟着一个奇对,排列方式一定是所有的奇对在左边,所有的偶对在右边,有用的信息只有奇偶对的个数。至此可以做一个集合到方程组解的一一映射,其中 表示第 段的奇对数, 表示第 段的偶对数,方程组如下:

显然两个方程是独立的,

环的版本

记环的版本的答案为 ,给出两种不同的解法。

容斥,显然 多出的部分是恰巧同时选了 ,这部分其实就是 ,故

Double counting,从两个方向数有序对 的数量,其中 是一种子集取法,遍历 的所有解, 中空对的编号,共有 个可能的取值,考虑先枚举 还是先枚举 ,可得

注意特判边界情况。

Comments

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

Problem D

First Solved:ldxxx

比较简单的多项式运算。

假设特殊点的权值分别是 ,非特殊点的权值分别是 ,显然

我们把边氛围分为三类:

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

总的边权

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

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

与上面类似

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

Problem E

First Solved:poorwill

先考虑莫比乌斯反演

我们要求的

幂方和可以用伯努利数预处理 ,然后 求值。

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

复杂度

Comments

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

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

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

Comments

interestingLSY

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

Xiejiadong

蟹蟹支持 刘队nb

卡题卡常卡精度

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

kimoyami

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

interestingLSY

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

interestingLSY

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

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

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

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

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

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

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