2020 年电子科技大学 ICPC 暑假前集训数学与几何专题题解

Posted on In

最后一个专题辣，结果到最后都没回成学校……前几个专题也都没写题解。

那就补一下最后一个专题的好了，有原题的还是会给出原题链接（

实际上原来是想插图的，但是感觉没啥意思，所以变成插 BGM 了，图就留在题解里了

题目简评

作为负责人还是有点义务谈谈这些题是怎么选出来的（并没有）。

对于数论部分，有 B, D, I, J, K, L, M 七道题，L 和 M 作为板子题不参与难度评价，剩下的题目中 B, I 两题比较简单，B 题的推导流程也可以作为入门推导过程。D 题涉及到结论证明与打表，可能对于刚接触的同学有些陌生。J 与 K 两题难度较大，其中 J 题是比较正统的数论题目形式，既要推大式子也要有一定的编码能力才能完成，若不熟悉 的话，K 题还是形式较为新颖的数论题。总体来说，数论题难度还是持平于上一次集训的难度。

对于组合部分，有 C, G 两题，C 题作为一般的组合问题难度还是较为简单的，G 题作为容斥原理的问题，有一定的推导难度，但是与去年三道板子相比，今年组合部分的难度要比去年的大。但是没有第二类 Stirling 数和 Lucas 定理的题，前者可以直接去做去年的题（虽然是板子……），后者的使用隐藏在 D 题的结论证明中，但是证出来的人很少……

对于博弈部分，有 A 题和 F 题，其中 A 题作为简单博弈，几乎人人都过了，F 题是博弈与组合的结合问题，难度稍大，但是理解了 NIM-k 问题后作出转化，实际上统计答案的部分还是比较好想的。总体来说博弈论难度和去年持平。

对于几何部分，有 N, O, P 三题，三道题难度递增，其中 N 题难度相对较低，O, P 两题来自 JOISC，难度较高。其中 P 题的结论比较难，O 题编码上要注意一些东西。但是相较去年的三道板子，难度还是比去年大的。

对于新加入的多项式部分和数学杂项部分，多项式部分有 H, Q, R 三题，其中 Q 题难度在三道题中较低，R 题其次，H 题很难。数学部分的 E 题难度不高，但需要一定推导。

总体来说，每个部分的题目难度均覆盖了从简单到难的范围（虽然有些部分不好放题难度跨度有点大了……），最低难度是 A 题，最高难度是 H 题。个人认为作为训练题还是不错的，难度对于入门来说较高，但低于实际比赛难度。

A - kiafa hynne mea?

题目描述

给定一个包含 个数的数组，Alice 和 Bob 两人在数组上玩游戏，Alice 先手，每次操作可以移除任意一个所有元素和为奇数的子段，Bob 后手，每次操作可以移除任意一个所有元素和为偶数的子段。当任意一方无法操作时判负。若双方均按最优策略操作，则最后谁会胜利？

数据范围：。

题解

结论是，数组内只要存在一个奇数，则 Alice 胜，否则 Bob 胜。

分三步考虑，如果数组中无奇数，那么 Alice 先手就无法操作，Bob 胜。

当奇数个数大于等于 时，考虑数组中存在偶数个奇数，那么 Alice 在每一个时刻都是可以取走数的，并且只取一个，而 Bob 一定会同时取走偶数个奇数，但是 Alice 的最优策略一定是第一次只取一个奇数，最后的状态必然是 Bob 取完后，数组变成很多偶数中有一个奇数，那么 Alice 在这次全部取走即可，Alice 胜。

考虑存在奇数个奇数，那么 Alice 第一次全拿走就好了，Alice 胜。

综上，当数组中奇数个数大于等于 时，Alice 总有必胜策略。

来自 Codeforces Round #429 (Div. 2) B. Godsend。

时间复杂度：，空间复杂度：。

Problem setter: Vingying

代码见这里

B- Was yant gagis chs hymmnos mea

题目描述

求

数据范围：。 的数据不超过 组。

题解

由题可考虑枚举因数，因为与 的 一定是 的某个因数。

其中 表示 之内有多少数与 的最大公因数为 。

考虑 ，那么 ，要统计这样的 的个数，即为 。所以

令 ，所以这是 与 的 Dirichlet 卷积，可记作 。

又已知 ，，所以可以写成 。

根据 Dirichlet 卷积的交换律与结合律，又可以写成 。

令 ，则

因为 ，所以 。 表示单位函数，即

这里的证明在 Möbius 函数介绍的时候基本都会讲，从略。

那么问题变成了 是多少。根据定义这个答案就是 。也就是说答案是 。

观察到数据范围给得很奇怪，大于 的数据很少，所以直接利用根号算法朴素做即可。但是也不能太朴素（比如直接按照求 那样改，每次循环除掉质数），否则会被卡。

其实复杂度这样是 级别的，一般来说是分预处理和根号两个级别的，这样可以平衡复杂度。

出题人表示这样是可以的，并没有卡。

我们枚举 以内的质数，然后类似上述方法做，复杂度更低一些（甚至快了 倍）。

复杂度更低的做法是利用 Pollard-Rho 进行质因数分解，但是 +jj 实现了一下发现比最朴素的暴力还慢不知道为啥（后来重写了一下跑得飞快）。

时间复杂度： 或 ，空间复杂度： 或 。

Problem setter: Vingying

代码见这里

代码见这里

C - yanje en yanje

题目描述

有一棵 个节点树，现要对树上每个节点染 种颜色中的一种，使得树上任意两个距离小于等于 的节点不同色，求染色方案数对 取模后的值。

数据范围：。

题解

考虑对于所有节点均满足：这个节点的颜色和所有与这个节点相连的节点颜色均不同。把这棵树当成一棵有根树，那么可以发现，如果一个节点 和它的父节点已经被染色，那么设 为 的儿子数，那么染 的儿子的方案数就是 。

因此 DFS 一下就好了。

来自 AtCoder Beginner Contest 133 E. Virus Tree 2。

时间复杂度：，空间复杂度：。

Problem setter: Vingying

代码见这里

D - Fou ki ra

题目描述

求

其中，，其中 为 Fibonacci 数列，。你需要处理 组询问。

数据范围：。

题解

这道题是 Vingying 翻数论教材翻出来的题

结论有两个：

  • ；
  • ，其中 ， 是一个奇数。

对于第一个等式详细证明已经遍地了，第二个等式是从四川大学数论教材课后习题里翻出来的（不过相信有很多同学打表打出来了……）。

第一个等式的证明从略，可自行参考网上文章。

对于第二个等式，根据条件，令 ， 是奇数，设 ，则有

可知，，由于左边只有一个质因子为 ，右边一定没有 这个质因子（ 为奇数）。由于等式左边组合数为整数，等式右边 为整数，结合 可知， 为整数。根据整除性质，考虑等式两侧，有

根据一条很显然的定理：若 且 ，则 。可以将上式写成

下面我们证明上式左右两边相等。

设 为一奇质数，且将 唯一分解后 的指数为 ，即 （ 表示完全整除，即 整除 而 不整除 ）。可知，。

将 转化为 进制，有

可知，，如果 的话就有 ，与 矛盾。

根据 Lucas 定理

其中 。

有

由于 ，可知 中一定无质因子 ，也就说明不含因子 。所以 。

也就是说，对于任意一个奇质数 ，我们都能找到一个组合数与其互质。那么对于所有的 ，有

因为 为奇数，则 一定能被奇质数唯一分解，也就是说

那么合并之，有

由 ，根据之前结论可知

可以说明，原式左右两边相等。

于是转化成了求：

显然直接求复杂度为 ， 来自求 Fibonacci 数中的矩阵快速幂。稍用优化（ 快速幂）后求值即为线性的。

可以发现，我们求值的时候只用了少量 Fibonacci 数（ 个），也就是说有很多重复计算的部分，我们可以统计重复部分个数，优化复杂度（这部分 Fibonacci 数可以打表，表也很小）。

还是根据第二个等式，如果枚举 ，则这个 对答案的贡献即为 ，其中 为 中奇数的个数。因此 。

所以根据以上结论计算即可。

时间复杂度：，空间复杂度：。

Problem setter: Vingying

代码见这里

E - nyamo!

题目描述

现在有三只杯子，一开始钥匙放在中间的杯子里，每一次都可以等概率地选择左右两个杯子中的一个与中间的杯子交换，求 次交换后钥匙在中间杯子的概率。分子分母约分后分别对 取模。

以 个数的乘积形式给出。

数据范围：。

题解

设 为第 次交换后钥匙在中间杯子的概率，由等概率选取可知有如下递推：

表示第 次交换后中间杯子内有钥匙的情况是第 次交换后中间杯子没钥匙，并且恰好选到了有钥匙的杯子得到的。所以利用乘法原理计算概率。初值为 。

但是 很大，所以要算通项。这个算高考常见题型了……

配凑等比数列

可知

但是要求先化简，然后分子分母对 取模后输出。

下面证明 ，过程如下。

分奇偶讨论，考虑扩展 Euler 定理。当 为奇数时

因为 是质数，因此上式成立。

因为 是奇数，且有 ，所以 ，那么

因此当 为奇数时，，也就是说 。

当 为偶数时

所以 ，那么

因此当 为偶数时，，也就是说 。

综上， 成立。

那么对 除 之后是否为偶数呢？因为 本身没有 这个质因子（因为它一定是奇数），那么除 之后一定仍为奇数，所以不会再与分母约分。

综上，输出分子为 ，分母为 即可。注意利用扩展 Euler 定理降幂后快速幂。

时间复杂度：，空间复杂度：。

来自 Codeforces Round #362 (Div. 1) C. PLEASE。

Problem setter: Vingying

代码见这里

F - Afezeria!

题目描述

在一个长度为 的一维棋盘上有 个白棋子， 个黑棋子，黑白棋子会按照黑白交替的顺序摆在棋盘上（先放黑棋）。现有两人 A, B，每次 A 可以选至少一个，至多 个黑棋子向左或右移动任意单位长度，每个棋子的移动长度和方向不需要都相同，但是要求不能在移动时越过其它棋子，也不能移出棋盘。B 移动模式与 A 相同，但 B 只能移动白棋子。A 为先手，两者均采取最优策略移动。求有多少种初始状态先手必胜。

数据范围：。

题解

可以发现，黑棋只能向右走，白棋只能向左走，当黑白棋中间没有距离后即为死局。

这个可以划归到一个 NIM-k 问题，将一对黑白棋中间（无重复匹配）的格子看做一堆石子，就成了 NIM-k 问题了，现在要求先手必胜状态数。

回想 NIM-k 中先手必胜的条件：只要存在某一位 的数目 ，那么这就是一个必胜态。但是这个并不好数，那就数先手必败的局面，再用总数减去即可。

设 表示当前状态到二进制第 位，棋盘还剩下 个空位的先手必败方案数。转移的时候，就可以枚举当前位放多少个 （ 的数量为 的整数倍），转移方程（大概）如下：

然后总情况减去必败情况即可。

来自 UVA 11758 Left Right

时间复杂度：，空间复杂度：。

Problem setter: Vingying

代码见这里

G - yasra dius manaf

题目描述

现有一 矩阵，初始没有颜色。现要给矩阵的每个单元格涂三种不同颜色中的一种，统计涂色后至少有一行或一列同色的染色方案数。对 取模。

数据范围：。

题解

对于二维容斥问题，我么可以类比一维情况实现。考虑有 行 列颜色相同，当 时，由于一定有交叉的格子，所以会有 个格子任意涂色。颜色相同有三种涂色情况。利用二维容斥可以得到的答案就是

这里还需要考虑 或 的情况，由于对称性只讨论一种后乘以 即可。只考虑有 行颜色相同，此时仍然利用容斥原理，方案数为

答案综合起来即为

后一个求和是 的，可以直接求值，但前一个是 的，直接算会超时。

考虑化简前一个求和式，具体过程是一段数学杂技。

忽略系数，考虑提取公共项

考虑后一个求和类似二项式定理，逆用之。

这样我们可以得到第一个求答案的式子

题解写的其实是与其等价的形式。

来自 Codeforces Round #493 (Div. 1) C. Sky Full of Stars。

时间复杂度：，空间复杂度：。

Problem setter: Vingying

代码见这里

H - Wassee fatere gyajlee deata

题目描述

一个环上有 个点，现要用 种颜色染色，每种颜色恰好染两个点，要求同色点间距离不超过 或等于 。定义一种安排方式的权值为被所有相对（距离为 ）且颜色相同的点分开的连续段上点的个数的乘积（若不存在相对的点，则认为权值为 ）。求所有安排方式的权值的和，对 取模。

数据范围：。

题解

这道题是整个专题里最难的了，而我只会抄式子。（因为 xydg 想听 Vingying 讲这道题）

先将其看成两排长度为 的点，也就是先把环先断开。

设 为给定长度为 的段，填满距离小于等于 的点对方案数，则有

其中 。这种情况的权值和为 。

设 表示中间存在距离为 的点对，但是没有距离为 的点对跨过这个点。这部分权值和为 。

设 表示中间存在距离为 的点对，但是存在距离为 的点对跨过这个点。这部分权值和为 。

考虑枚举中间距离为 的点对位置，则 的递推关系如下：

最后考虑环上的情况，也就是两边都是相对消除的情况，然后两边跨越这种点。设这部分权值为 ，递推关系如下：

可以发现，求 的时候必然需要后面的某些项。对于这种问题可以利用分治 NTT 解决。

ldz, yyds!

来自 Codeforces Round #431 (Div. 1) E. Days of Floral Colours。

时间复杂度： 或更优，空间复杂度：。

虽然我想直接放 但是 Vingying 还是拒绝了，良心出题人

因为有 甚至还想出 ……结果又被拒绝了

Problem setter: Vingying

代码见这里

I - An Easy Math Problem I

题目描述

求

的值， 表示 的小数部分。请对 取模后输出。你需要回答 个询问。

数据范围：。

题解

看起来很好搞，首先只考虑 的情况。

记

对于 ，可以化为

对后面做一个前缀和，然后线性统计答案即可。

对于 ，可以参考计算机 · 关于数列求和与等差子序列计数问题的一些探究，结论是

其中 表示 的约数个数。

那么答案就是 。

约数个数，乘法逆元都是可以线性求出的，因此在线性时间复杂度下预处理所需值即可，每个回答都可以在常数时间内处理。

时间复杂度：，空间复杂度：。

来自 洛谷 P4900 食堂。

Problem setter: qqq17770027225

代码见这里

J - An Easy Math Problem II

题目描述

求

的值，对 取模。你需要回答 组询问。

数据范围：。

题解

仍然考虑枚举

有经验的话可以看出后面是一个经典求和，来自 JZPTAB 一题（BZOJ 2693）。

令

接着枚举因数

其中 。那么单次回答

即可以在两次数论分块的时间复杂度下求出，是线性的。

线性的肯定不行，所以考虑预处理掉 ，然后数论分块。预处理 的过程是 的，那么只做外面的一层数论分块即可，复杂度为 。

挺显然结果还是不行，考虑变换式子

交换求和顺序

考虑换一下字母。因为 可以遍历 的整数，所以

利用线性筛可以预处理后面看起来很诡异的求和部分，因为是积性的。其实原来做个 的类 Eratosthenes 筛就行了，但是上一道题没卡这个方法，这道题就卡了。结果卡上头了，std 754ms 时限 1s 实属屑题。

但是我写的这版时间 400ms 多，因为稍微加了点常数优化。

然后就可以利用筛出来的东西数论分块了。

时间复杂度：，空间复杂度：。

bonus: 如果求和号有 个，每个变量的指数为 ，应该怎么做。

Problem setter: qqq17770027225

代码见这里

类 Eratosthenes 筛代码见这里

K - An Easy Math Problem III

题目描述

求

的最小整数解。

数据范围：。

题解

首先直接解模意义下解二次方程是错的，因为 可能在模 意义下没有逆元。

那么我们将模数分解质因数，现在模数形式为 ，做好之后用 CRT 合并回去即可，但是还是存在 在模 意义下无逆元的情况。

实际上，这个问题是求伪 Smarandache 函数 的值。在 OEIS 上可以查到这个数列。在 2002 年 David Gorski 的论文 The Pseudo-Smarandache Function 研究了它的求值问题。但是有两个 Case 没有解决，还有一个 Case 是错的（c 点是错的，对比 2008 年的论文不难发现其中奇数应改为质数，左侧表中 时答案应为 而不是 ）。更好的论文是 2008 年的 A note on the Pseudo-Smarandache function，但求值还是不能包含所有 Case，并且比较复杂。

那么我们换一种考虑方式，显然我们求的是 的一个最小正整数解，其中 。因为 ，所以对于 中的质因子与它们的幂次，不是来自 就是来自 。先不考虑 的影响，因为小于等于 的正整数中，质因子最多的数有 个质因子，我们就可以对这 个质因子与它们的幂次暴力枚举属于 还是 。

再加入 的影响，考虑 ，其中 ，令 ，，则 成立。考虑到大小关系，不妨令 ，则 。则现在求 的最小值即可。由于枚举 ，则要求 最小。这是经典问题，利用扩展 Euclid 算法解决即可。

更优的复杂度是枚举 的因子后利用扩展 Euclid 算法解决，给出的题解也是按照这种方法写的。

最优的复杂度应该是对暴力枚举质因子的过程进行折半（选出了这个位置属于某个数，其余的自然属于另一个，并且这个过程是对称的），可以将指数位置除个 。

来自 Comet OJ - Contest #10 C. 鱼跃龙门。

时间复杂度：，空间复杂度：。

草，你跟我说这事简单题

结合论文可以搞一堆特判。

Problem setter: qqq17770027225

代码见这里

L - Kanade Loves Calculator

题目描述

求方程

的最小非负整数解。

数据范围：。

题解

扩展 BSGS 板子题，用 map 被卡了。

啥事扩展 BSGS 捏，用 BSGS 的时候发现 ，这时就需要用到扩展 BSGS 了。

详细介绍可以参考网上博客或 BSGS - OI Wiki。

时间复杂度：，空间复杂度：。

Problem setter: HeRaNO

代码见这里

M - Victorique aime les fonction

题目描述

给一个数列，多次询问某段形成的幂塔对 取模后的值。

数据范围：。

题解

看见幂次很大的形式，一般做法是利用扩展 Euler 定理降幂。

上式在 时成立，请注意定理使用条件。

我们迭代 ，最多迭代 次 就会变成 。而正整数对 取模均为 ，所以指数就可以在 的时间下递归处理了。关于这一结论的证明，可以参考 On a function connected with 这篇论文。

由于定理使用时要求指数部分大于 ，在模意义下无法判断大小关系，但只要某个时刻这个数比 大，那么接下来的任何时刻，如果不遇到 的话，这个数都会比 大，因为是求幂。所以对于取模运算，可以定义为如果这个数比模数小，则返回原值，否则返回这个数对模数取模后再加模数，以满足扩展欧拉定理的使用条件。

最后利用快速幂计算答案即可。

对于每次求 的过程，可以预处理 以内所有数的欧拉函数值，而不用每次用 的复杂度求取。但是 的复杂度过了也不知道为啥……（验题的时候测过，并且都 T 了……

来自 Codeforces Round #454 (Div. 1, based on Technocup 2018 Elimination Round 4) D.。

时间复杂度：，空间复杂度：。

Problem setter: HeRaNO

代码见这里

N - 地学部の部活

题目描述

求平面上 个点组成非平凡三角形的面积和。

数据范围：。

题解

考虑利用叉积表示三角形的面积，这样三角形是否平凡就不用处理了，但发现有个向量减法不好表示。

既然数据范围允许一种平方复杂度的做法，我们可以枚举原点，只计算与原点形成的三角形的面积和。现在就可以化成两个向量的叉积的形式之和了。

现在的问题转化成了平面上有 个向量，求任意两个向量的叉积的模之和。请注意顺序，先取模再求和。

在实数域下，这个问题我们是有 的做法的：

先对 求一遍后缀和，然后线性统计答案即可。

在二维向量空间中，由于叉积具有对加法的分配律，上述等式仍然成立。

但是取模没有任何性质，展开也是很困难的事情。如果让所有的叉积都是同号的，那么我们统计答案就可以直接去掉模长，将纵坐标加起来了。所以按照极角排序，让按以上顺序求值的所有向量叉积都是正的就可以了。

根据观察，为了避免重复统计答案，可以只统计枚举到的原点右侧的点与其构成的三角形面积和。

由于所有点坐标都是整数，所以面积之和的二倍一定是整数（两整数相乘一定是整数），那么面积和要么是整数，要么是整数加 的形式。输出时判断一下即可。

来自 POI 2008 Triangles，BZOJ 1132。

时间复杂度：，空间复杂度：。

Problem setter: HeRaNO

原来是想自己出一个的，然后就没有然后了

代码见这里

O - 地学部の部活 · 改

题目描述

平面上有 个点，每个点有三种颜色。求不相交的三色三角形的对数。

数据范围：。

题解

如果两个三角形不相交，则一定可以做出两条内公切线，如果相交或内含是做不出内公切线的。三角形的公切线可以类比圆的公切线。

先枚举一个原点，记为 ，以这个点为极点，过这个点且与 轴平行的直线作为极轴，建立极坐标系，把剩余点按极角由小到大排序。然后统计出在极轴上方和下方的每种点的个数。

然后根据点枚举公切线，记枚举到的点为 ，初始时公切线为极轴。开始统计。那么一定存在一条公切线过点 和点 。因为公切线与三角形不相交，所以一方选择公切线上方的点，另一方一定选择下方的点。然后利用乘法原理统计方案数即可。

统计完后转公切线，那么点 一定改变了相对于公切线的上下位置，而其他点不动，应该只将它的位置信息改变。

这样，可以发现，同一对三角形最终被统计了 次，就是同一条公切线会被枚举两次，最后做出的答案应除以 。

来自 JOISC 2014 Day4 T1「2 人の星座」，LibreOJ #2882.。

时间复杂度：，空间复杂度：。

Problem setter: HeRaNO

代码见这里

P - 地学部の部活 · 改二

题目描述

平面上有 个点，一部分被染 ，一部分染 ，另一部分没有被染色。称一种染色方案是合法的，当且仅当：

  • 所有点都被染色成 或 ；
  • 存在一种连线方式，使得相同颜色的点互相连通，并且构成一个星座的线段不与构成另一星座的线段相交。

求合法染色方案总数。

数据范围：。

题解

结论是：一种染色方案合法，当且仅当这 个点的凸包上的两种颜色点分别连续。

这个结论是 IOI 2006 Points 一题提出的。

证明分两部分。必要性是显然的，枚举合法染色方案观察即可。

充分性证明如下：考虑对于一个不同色的非平凡三角形，则一定有一种颜色的点有一个，另一种有两个。将那种颜色唯一的点记为 。若三角形内所有点均同色，则任意的连接方式都是合法的，若内部两种颜色的点均有，则可任取与 颜色相同的点，将这个三角形剖分为三个小三角形，直到任意三角形内部颜色均相同为止。划分后连接选择的点与 点连接。

可知，这个划分过程是有限的，并且一定会在合法状态停止的。

然后考虑一个凸包，由于两种颜色点分别连续，我们可以划分出两段连续区间，在区间内部所有点颜色均相同。对其我们一定可以进行一种三角剖分，使得任意三角形均为非平凡不同色三角形。

因此充分性成立，原命题得证。详细证明可以参考原版日文题解。

然后就是在凸包上转一圈染色，凸包内部的点均可以染两种颜色，两部分乘起来即可。

可能出现空集的情况，需要在代码中特判。

译自 JOISC 2012 Day2 T2「星座」，LibreOJ #6717.。

翻译完之后发现网上没有中文题解，也没看懂日文题解。看懂了之后发现网上已经有中文题解了……

时间复杂度：，空间复杂度：。

Problem setter: HeRaNO

代码见这里

Q - 美食殿堂的副业

题目描述

给出一个数组 ，对于它的所有非空子集，求所有子集前 小元素之和的和，如果集合没有 个元素则其余元素补 。对于每个 都要输出答案。

数据范围：。

题解

可以分别考虑每个数作为第 小出现的贡献。

首先对 数组从小到大排序。因为 需要作为集合中第 小出现，所以这个集合至少有 个数，比 小的选择 个进入集合，剩下比 大的可选可不选，这样就是 种选择。总结起来，用 表示所有数作为集合第 小的总贡献。 可表示为：

朴素做法是 的，会超时。

考虑如下变形：

显然这是一个卷积形式的式子，令 ，则将 数组翻转一下与 数组求卷积即可。

最后答案注意一下答案的位置（做完卷积之后还要将那个数组翻过来，这里是考虑 数组下标和 的对应关系相同），并且系数乘进去就行了。

来自 HDU 5829. Rikka with Subset。

时间复杂度：，空间复杂度：。

Problem setter: HeRaNO

代码见这里

R - 终章：真正的字符串

题目描述

定义字母的另一个顺序 ，求在两种顺序可以混合使用的情况下 串在 串中的所有匹配位置。

数据范围：。

题解

用 FFT 做的字符串匹配。用 bitset 被卡了，用定值 NTT 也被卡了（要对字母随机权值，这个视频有讲……）。

稍微需要一点复变函数的知识。

xydg：卡哈希大成功。

来自 Educational Codeforces Round 85 (Rated for Div. 2) G. Substring Search。

记 ，则时间复杂度：，空间复杂度：。

Problem setter: ZXyang

代码见这里