那个寒假，从 ITMO 训练营回来，我感觉到从未有过的蜕变

我们在2019年的寒假，参加了 2019 ITMO Chinese Winter Camp ，十几个队伍在北京连续进行了六天的训练。

每天都是早上起床打比赛，下午听题目分析，晚上补题，就这样连续六天的训练生活，感觉异常的充实。

ITMO 是 ICPC WF 七冠王，他们训练营的题目虽然不是原创题目，但是题目质量相当高。

今天我们来看一套 2019 ITMO Chinese Winter Camp 训练题。

Problem A

题意：给一个

的矩形染上两种颜色，每次只能给连续的一部分染上一种颜色，要用最少的次数染成指定的图案，求不同的方案数。

题解：先根据色段的个数分为奇偶两种情况：

奇数：

不是一般行，我们考虑

这样的情况，显然我们会在第一步全部染上

，这样的话，中间的一段就变成了有底色

的

，我们考虑

表示有

个

的时候的方案数，显然

，我们考虑最后一个被染色的位置，显然不是最旁边的两个

，所以会有

个选择，发现，无论最后染色的是哪一个位置，都可以把

问题变成

问题。所以就得到了递推式子

。

偶数：第一笔一定是从一端染向一个位置，这之后一定有一笔从另一端跨过第一笔的终点染向一个目标图案的两色交界处。

先枚举两色的交界处，这样就把这个问题转化为了奇数问题的子问题。如果左右染色后分别还有还有

个和目标图案不同的色块，如果先染左边，右边

步可以和左边剩下的

步自由组合，组合数

乘上染

和

个色块的方案数

，再乘上第一笔终点可能的位置数，就是先染左边的方案总数。同理可以推出先染右边的方案总数，再对每个可能的交界处的情况求和，就能得到答案。

Problem B

题意：人分成左右两队，左边n个右边m个。总共有r种消息，左边和右边的人各自知道一些消息，左边的人可以挑选右边的一个人问一个自己不知道的消息，由右边的人挑选告知的消息。同一个右边的人可以被多次询问。求问是否存在一个方案使得无论右边的人怎么捣乱左边也能问出所有消息，能则输出方案。

题解：考虑在已经形成的方案上让右边的人反悔，使得问不出某个消息，发现如果左边的人问的消息可以由两个及以上，则怎么着都是无效的询问，如果有效地问出a（有效指没有这个人问就问不出这个消息），则可以让右边的人反悔告诉你b。让左边地人二分图匹配到左边的人都不知道的消息，当且仅当左边的人通过某人只能问到j，则连边。建图地复杂度看似是

，但场上本着莽夫地心态加了break就交上去过了。。实际上可能很难构造出加了break还循环跑满的情况

Problem C

题意：给出平面上

个点，求出一条直线使离它距离相同的点最多。

题解：如果枚举直线斜率计算距离取重复出现次数最大的两个，复杂度是

，会超时。

正确的做法是直接对两点连成的

条直线进行处理。首先将完全相同的直线合并并保留重复出现的次数，再通过出现的次数推出这条直线上有多少点。然后，再对斜率相同的直线，取出包含点最多的两条，用点数和更新答案。这样的复杂度是

的。

需要注意的是，如果一种斜率的直线只有一条，此时如果还有直线外的点，答案应该更新为直线上点的数量

，否则更新为

。

Problem E

题意：一个位置

分别向

和

有两条路，如果两条路径等长，随便选一条走，否则就走短的一条，求走到

层的路径长度期望。

题解：直接利用期望的可加性，

表示走到位置

的路径期望，分哪边路径长或者等长三种情况转移即可。

Problem G

题意：定义

为斐波那契数列，求

思路：看到不一样的模数直接素因数分解，求出答案对各个因子取模后的答案再使用CRT。注意斐波那契数列模某个数是有周期性的，于是预处理一段完整周期以后分段求和。

，因此预处理的复杂度在

以内，100组数据完全够，之后再用CRT合起来。k可以用欧拉定理模一下，略微有点卡常。

Problem H

题意：定义字符串hash函数

，求长度为n的字符串，模数为p，hash值为x，模数为m的情况下可能有多少种不同的字符串，结果对998244353取模。

思路：考虑

为长度为i，hash值为j的情况数，发现合并段字符串类似取卷积的操作。将hash的计算公式拆成两半，固定hash值为x，则要求前一半和后一般的值加起来模m正好为x。不过前面一段的hash值需要先乘上一个值

。剩下的就是利用快速幂的思想将长度n看作乘法的幂，一步步合起来，再运用NTT算卷积，并且将m ~ 2m-1合并到 0 ~ m-1。总复杂度

场上容易想到解法，然而实现的时候在函数里开大数组导致无端RE，WA，自闭。

Problem I

题意：求区间

之间出现次数最多的特征值，一个数的特征值是对这个数不断的做数字和，直到

，这个

的值就是这个数的特征值。

题解：

方法1（数位dp）:显然，经过一次数位和的处理，这个和不会超过

，先暴力处理

的特征值。

接下来的问题就是如何统计区间

内的所有数字和出现的次数。

先预处理

表示位数为

，和为

的方案数，然后对区间做差分，直接dfs一遍就能算出来。

方法2（找规律）:如果打出特征值的表，会发现特征值是一个

~

不断循环的列表，也就是

的特征值是

因此只要求出

的特征值，接下来的

个数就是出现最多次的特征值。

Problem J

题意：显示器只有两位，当这个数

时，只会显示

，求两个数，每天同时减少

，多少天后，两个显示器上的数为

倍关系。

题解：

方法1：大力讨论，很复杂，但做出来了。

方法2：两个数如果都

的话，他们显示是相同的，如果倍数不是

，那么必然有一个数

，那么先把较小数调整成

，然后直接暴力枚举就行了。

Problem K

题意：构造一个背包问题，使得其解是

的倍数，如果无法构造输出

。

题解：不存在无法构造的情况，直接构造解是

，背包大小为

的背包问题，分两步。

第一步，添加小的物品（大小等于

或

)让

数组中下标小于

的数的数量级均匀分布在

到

之间，其他位置留

。

第二步，添加大的物品（大小大于

）如

将

的值加到

中，同时不对其他位置造成影响。在取的时候，只要按照

的大小依次贪心取最大的就可以了。