写在前面 作为一个不是特别专业的出题人，之前只在牛客上面出过挑战赛和练习赛，因此出提高组的经验属实欠缺。在出这场题之前一直在思考到底是要出一些超出考纲比较多的题目还是老老实实按照往年的难度来出这套题。 思前想后还是决定去参考往年的难度来出，然后发现提高组难度并不高，所以这套题也是出的有点迷迷糊糊。尤其在比赛过程中我意识到这道题实在是过于简单，如果把换到然后再加一道防的题目可能这套题看上去会更好，可惜错误的预计了模拟赛的难度和选手的实力，导致这场题的难度变得偏低了。 Problem A. 三元组计数 本来是想出一道数论的套路题，利用整除分块的性质来进行计数，写...

A.大吉大利 我们按位考虑，那么每一位的贡献就是在二进制下这一位在个数中出现的次数的平方乘上二进制的系数。 https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43254017 B.三角形周长和 也是一道签到题，但是边长改成了曼哈顿距离，至于为什么，完全是因为我不想写std去判精度。 因为是1000，所以直接去枚举所有边，那么每一条边显然会在其他个三角形中出现，这个就是这条边的贡献系数，这题就算完了。 https://ac.nowcoder.com/acm/contest...

A.牛牛与序列计数 找规律或者打表不难发现答案。 那么当为奇数时,当为偶数时。 推导的话这里给出一个生成函数的推到做法，对于红色和蓝色，不难发现生成函数都是，对于黑色和白色，生成函数都是。 两种都是经典的生成函数，分别为和。那么答案是展开后的系数，我们对这个式子化简后泰勒展开可以得到答案是。 https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43043882 B.牛牛与组合数学 现在直接算出不太靠谱，我们考虑用质数来随机测试。 我们可以取个质数作为检测质数，然...

A.Forsaken喜欢数论 很显然， 可以在线筛过程中维护出来，所以我们只需要做一遍线筛维护出所有 ，然后求和就行了，复杂度 . https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41517619 B.Forsaken喜欢字符串 对于每个询问，本质上是求其他所有串的长度为的子串是串的子串的个数，然后总数乘上就是答案,注意到特别小，因此我们只需要存下每个串的所有哈希值，并且记录这个哈希值出现的次数，然后每次查询哈希值出 现的次数就行了。复杂度是。 https://ac.nowc...

本来在赛场上推完了公式，不是实现难度有点高，20多分钟根本rush不完，我太难了。 对于和来说当的时候只需要做质数个数和以及质数和两个就可以解决问题了，当时我们直接暴力就行了 //author Forsaken #define Hello the_cruel_world! #pragma GCC optimize(2) #include<iostream> #include<algorithm> #include<cstdio> #include<string> #include<cstring> #include&l...

就是求所有的子串满足是的子串并且不存在子串使得子串和子串相同且子串的反串也不和相同。 首先我们考虑这个条件，这个条件说明和都是本质不同的子串。因此我们肯定是考虑求出串中本质不同的子串，然后想办法减掉这些本质不同的子串中，通过能够得到其他子串的一类子串的数量。想到这里，我们就可以把问题转换成求和的公共子串数量。但是考虑直接这么做有点困难，我们考虑转换一下问题，如果说一个子串能够通过反转得到中另外一个子串，那么我们可以肯定，该种串只能对应一种子串，那么我们考虑将连接到串后面，并且在中间添加特殊字符。那么对于新串，在串通过反串不能得到其他子串的一类子串可以形成的贡献，而对串中可以反转并且得到其他子串...

比赛的时候被的特判卡的太久了，都没有看这个题，赛后想了一会儿发现这个题和上某场的E十分相似。这个题能胜利的区间应该满足一个比较特殊的性质，我们设这个区间的最大指为，那么只有当区间的和大于的两倍时，这个区间才是满足胜利性质的条件。 我们考虑分治做法，当我们枚举一个区间到时，我们先找到区间最大值的位置，然后我们设满足答案的区间是包含这个最大值的，因此我们只需要固定一个左端点或者右端点，然后二分去查找另外一个端点的位置，就能统计答案了，这个做法实际上是十分的显然。接下来，我们先设最大值的位置为，因为我们已经处理了这个最大值所能影响的区间，接下来我们只需要解决不包含这个最大值的区间我们就能得到子区间的...

这个题算是一个比较裸的回文树了，至少我当时第一想法这是个模板题。 首先我们需要知道一个十分显然的结论，对于一个长度为的回文串，最多只有不超过种本质不同的回文子串，知道了这一点我们再来考虑怎么处理这个题。 对于一个回文树，我们可以得到的信息有这个节点所代表的回文子串在整个字符串中出现的次数，这个恰好是该题解题的关键。考虑回文树的构造过程，仔细观察可以发现当我们添加一个字符时，只有当产生本质不同的回文子串时，才会产生新的节点，否则我们只需要在对该回文节点的加一就行了，因此，我们可以在构造回文串时顺带把该回文子串的右端点加入，这样我们在统计答案时，就能得到该回文串在原串中的左右端点。然后我们只需要对...