历次考试总结：

0327

今天袁老师发布了一系列的通知，总的来说就是要我们用博客来写每日总结。

正好今天是搬家的日子，在八方住了三个月终于回幸福桥了。

第二题仍然是80分，这已经是未解之谜了。我问了张明驰，看了他的代码，然后照着改，最后几乎是抄了，但是仍然是80分。后来偶然的一瞬间我发现了一处不同。这是本质的不同，是对我没有把算法想清楚的惩罚。欢天喜地地改了，提交，AC！我开心极了，比顺畅地做出了一道题还高兴。

这道题中，对于方程\(ax \equiv c (mod\ b)\)在\(\gcd(a,b,c) \ne 1\)的情况下把\(a,b,c\)同时除以了\(\gcd(a,b,c)\)后，我只把exgcd得到的x变成了\([0,L)\)内的值，但是因为模数是b而不是L，所以应该变成\([0,b)\)。居然只错了2个点，害的我以为是少了特判。

然后就看到了第三题。一开始我以为这也是一道基础题，没想到居然要用到莫比乌斯函数！这种东西怎么可能靠几个资料和自己上网找来完全弄懂啊！我当时寒假听课都是晕晕乎乎的，几个月之后复习才渐渐地弄懂，现在出现在这里，不是在挑战同学们的心态吗！虽然去年的这个时候2018届的早就掌握了这些知识了。不过，看群里在讨论“互质那题”，不知道是不是那道。文尔玉似乎试图用卡常把这道题做出来。勇者啊！

0328

今天想要尝试一下J题，但是想了一会发现这道题比看起来难得多。回到排行榜发现没有一个人做出了这题，于是就果断放弃去做A题。之后又去做余数求和。

0331

今天的信息学习很顺利：因为以为数论26题的比赛要结束了，而且被袁老师点名批评：“这三个人怎么做的这么慢”。正好我想着要反超，于是我就在一个晚上一连做了5道题。虽然都不难，而且我也并没有反超谁，仍然是倒数第三，但是我还是很高兴。

其他的就没什么了。明天主要要做的是补作业。

0401

愚人节真是一个奇怪的节日。

我的名字变成灰色的了。这应该是洛谷的一个玩笑。

0402

昨天晚上我没有做题，在补常规作业。

今天要多补几道题了。但是连续看了四五道题，都没有一道会做的。

我的疯狂被屠

本来以为要用矩阵做，在思考了半个小时之后得出了“矩阵快速幂不能求二次项”的结论。我觉得此题无解而上网查题解，发现这道题要用到的是斐波那契数列自己的性质！而且需要数形结合。

0403

一连看了三道题都毫无头绪，我决定去学习没有学完的PPT和PDF。看着看着就睡着了，太难了。

0329

今天是星期六，袁老师把我们召集到了李思齐和刘振西租的宿舍里，搬了几张凳子和桌子，拿着我们自己带的笔记本电脑，上午考试下午改题。

十分欢乐。

考试的题

set

一次操作的定义为：从集合S中选出两个数\(a_i\)和\(a_j\)，然后把\(a_i+a_j\)加入到集合S中。

给出初始的集合（大小<=1e5）和操作次数k（k<=1e9），求在k次操作后S中元素之和的最大值。注意S中的元素可以为负数。

这道题我的算法是正确的。分类讨论和斐波那契数列。

但是只有90分的原因是一句printf("%d\n", sum % MOD);。改成printf("%d\n", (sum + MOD) % MOD);就好了。时刻要记得，模运算下很容易出现负数。

candy

在一个平面上有一些点，每个点都有一个颜色。你可以随意选定一条斜率为0的线段，并选取该线段正上方或者正下方区域内的所有点（包括边界）。在选定的点集中没有包括所有的颜色的情况下，求最大的可以选定的点的数量。n<=100000。

本来以为这只是一道比较复杂的数据结构题，但是写着写着发现不对劲，代码越来越长，到后面陷入了混乱。我发现这道题有多种解法，要是把它们弄混了就麻烦了。

第一种：袁湘韬的单调栈

首先考虑取正下方的部分，而且不取某一种颜色t。

所以，问题转变成，找到一个包含最多点的矩形，保证它的底边在全图的最底部，而且没有包括任何颜色为t的点。这个和最大全0矩阵有点像，也可以用相似的方法来解。

维护一个y坐标单调上升的栈。如果新加入的点的y坐标低于栈顶，那么栈顶就可以被弹掉，然后这个被弹掉的栈顶就可以计算答案了：它在栈中的相邻元素和新的元素，三者可以得到一个方框。

第二种：李思齐的算线段（和正解相似）

因为矩形的底边在全图的底部，所以一条线段表示矩形的天花板，就可以确定一个矩形。从每一个点向左边和右边延伸出去的线段都可以提供一个答案。重点在于计算这个答案。

从k号颜色延伸出去的线段表示的矩形当然就是不能包含k号颜色，所以它的左右边界就是最近的y坐标比它低的同色点。这个可以用一个线段树维护。

第三种：题解

。。。。太凌乱了。

game

在一个n格长一格宽的棋盘上，有k个棋子，k为偶数，其中一半白一半黑。最左边的一定是白的，最右边的一定是黑的，中间黑白相间分布。

每次操作可以把自己的1~d个棋子进行移动，每颗棋子都随便什么方向什么距离，但是不能越过其他棋子，也不能越过边界。先手走白子，后手走黑子。

给出n,k,d，问：有多少种初始情况，先手必胜？

k<=100, n<=10000

我见过的博弈论最难的题。一定要改出来。

有30分的数据点k=2。也就是两种颜色各一颗。显然，只要白子和黑子一开始没有挨在一起，先手就是必胜的。所以答案就是\(C_n^2-(n-1)\)。

对于更多的，我想了很久，最终还是没有想出来。我想过每对白子和黑子之间的距离是否有关，包括相邻点的对数和的的关系等等。大多是乱想。

袁湘韬的乱搞

他知道如果\(\frac{k}{2}=d\)且有点对不相邻，则先手必胜。如果不相邻的点对可以在第一步就被先手合到一起，那么先手必胜。所以，他认为可能先手必胜等价于\(1\le不相邻点对 \le d\)。40分，比暴力多10分。

李思齐的有意骗分

他知道如果\(\frac{k}{2}=d\)且有点对不相邻，则先手必胜。所以他就假设所有数据点都满足\(\frac{k}{2}=d\)。真的就碰对了一个点，多得了十分。

正解

https://blog.csdn.net/weixinding/article/details/7321139

上面是关于多操作Nim游戏的讲解。

这个问题确实要从每一对黑白子之间的距离入手。但是，你要把它转化为已知的模型。在这个问题中，从30分的思考中可以（？）启发出来一个思想：白子向左走和黑子向右走都是没有意义的，因为它所对应的子可以马上追上相同的距离，导致两者之间的距离不变。

所以我们只考虑白子向右走和黑子向左走。这两种行为都会导致两者之间的距离被消耗。这样的一个距离可以被视为是一堆石子——而\(\frac{k}{2}\)对黑白棋子就可以被视为是\(\frac{k}{2}\)堆石子。石堆的大小是对应的黑白棋子之间的距离。

问题转变成：有\(\frac{k}{2}\)堆石子，每个人可以任意在其中挑\([1,d]\)堆，并在每一堆中拿走任意个石子。首先无法操作的人失败。

这个就是多操作Nim游戏。（名字是我自己取的）

它的胜负判定标准是：把每一堆石子的大小表示为二进制之后，每一位分别相加，再模\(d+1\)，如果每一位模完后都是0，这种场面就是必败状态。否则就是必胜。

这个的证明就是普通Nim游戏的证明的扩展。链接里的讲解很完整。

好了，学会判定一个场面是否必胜了，但是我们要求的是一共有多少个必胜场面啊？

通过一段时间的推式子发现行不通，于是决定递推（或者说DP）。

递推也是很有技巧的。

\(f[i][j]\)表示二进制从低往高的前\(i\)位中，一共使用了\(j\)颗石头（Nim游戏的石头）的必败方案数（因为必败比必胜好求）

既然是必败，那么这\(\frac{k}{2}\)个数的第\(i\)位上的1的总个数一定是d+1的倍数。假设是q倍。那么，第i位新增的石头个数就是\(2^iq(d+1)\)个。

\[f[i][j]=\sum_{0\le q且j\ge2^iq(d+1)}f[i-1][j-2^iq(d+1)]\times C_{\frac{k}{2}}^{q} \]

0329（未完成）

考试

mining

给出一棵无权无根树，一个\(K\)，一个序列\(d_1,d_2...d_{n-1}\)，你要选择一些点建造仓库。在每个点建造的费用都是K。每个没有建造仓库的点的运输费用是\(d_{dis}\)，其中dis指的是这个点到最近的点的距离。

请最小化费用。n<=100

我一开始还犹豫了很久，因为仓库可以影响到该点的孩子节点的费用，所以有后效性。

但是这个后效性是可以被表示出来的，跟以前讲的那道最难的树状dp一样。

首先讲部分分：有20分的部分分是该图是一条链。

这道题应该用很多个区间的答案加起来，每一个仓库控制一个区间。你可能会问：如果上一个仓库与本区间的开头元素距离更近怎么办？我算的是这个开头与当前这个仓库的距离啊？答案是：这样的情况是会被枚举到，但是因为它肯定不是最优的，所以会被忽略。所以就是f[i] = min{f[j] + w(j + 1, i)}，其中w(j + 1, i)要用O(N)的时间求，就是枚举这个区间内的仓库的位置，使得该区间内的总价格最小。

正解和这个的思想不同。你要联系到战略防御上去。

用\(f[i][0/1][j]\)表示 i 号点被一个距离它为j的仓库覆盖，如果第二项为0则表示这个点在 i 的子树的外面，1则表示在子树里面。转移方程如下：

candy

给出一个数列\(a_1,a_2\dots a_n\) ，你现在手中有另一个数列b:（有n项）\(m,0,0,0...0\)，其中\(m=\sum a_i\)。你可以做的操作只有：挑选两个位置 i 和 j，必须保证\(b_i\)是偶数，然后令\(b_i=\frac{b_i}{2}\)，\(b_j=b_j+\frac{b_i}{2}\)。（也就是把\(b_i\)对半分，一半留下来，一半给\(b_j\)。）

愚人节比赛带给我的世界观颠覆

本来就不想参加今天的这次洛谷愚人节比赛。这是一个需要脑洞的东西，而天生思想保守没有创造力的我是不可能有那么大的脑洞的，看这个题目只会糟心，受到挫败。

但是整个机房的人都在愉快地讨论这次题目，所以我也去看了看。所有题目都是不知所云，看得我头疼，而且越来越暴躁。

第一题：给出一个100000以内的数f，输出f对应的特殊的数。

但是题目并没有给出特殊的数是什么意思。他只说特殊的数包括938844353，19260817，114514之类。而5个样例也是完全没有规律。

但是李思齐一声高喊：我直接输出f*700就AC了。我也试了试，AC了。原来就是输出任意数啊。

后来根据CYJian自己在知乎的讲评中写的吐槽，才终于知道这道题是要输出 f 的 任意倍数。

第二题：给出一个可执行文件，写出源程序。

全洛谷都没有人写出来。不想了。后来看了题解——各种计算机术语，极其复杂的推理，还有令人崩溃的“显然可以猜到”，真的看不懂。

第三题：输出洛谷管理员zhouwc加入洛谷公司的时间。

但是我不知道啊。但是为什么这么多人都AC了？

第四题：题面给出一首写到一半的不知所云的猎奇的英语诗，请把它写完。

？？？？？

后来发现题面是藏头诗：Output Author Name。

而且作者的名字的o还不是英语o，而是俄文的o。所以必须Ctrl+C才能AC。

第五题：给出一份代码。没有输入规则。没有输出规则。

？？？？？

第六题：给出一些可能被微调过的数据，根据数据猜测这是洛谷里的哪道模板题。

wcnm。吃力不讨好的事情我不做。

第七题：一个全都是东方梗的题目。输出袜子商店的最后的收益。当然与东方人物有关。

这种鞋垫游戏我可不敢深究。

第八题：给出一些洛谷的课程，和一些人报的洛谷课程，求kkksc03一共赚了多少钱。

太麻烦了。不过这道题总算正常了一点。洛谷课程都是真实的，你要自己上链接去找价格。

第九题：用传统题的方式实现提交答案题：输出一个九位数。一个英语单词，首字母大写。一个只包含大写字母和符号的字符串。一个五位数。一个矩阵（不要输出行数和列数）。

？？？？？？？

正像我所预料的，这些题都是不知所云。我受不了这些鄙视我的创造力和心态的东西，于是我成为机房里最后一个加入，第一个退出这场比赛的人。

但是，重点的东西反而被他们忽略了。

zhouwc是noip2018提高组一等奖。也就是说他现在最老也是大一。

而且CYJian参与了命题。还有一个我很早就知道的，chen_zhe也很年轻，但是结果今天是同学们告诉我chen_zhe和我们一样大。而且还用“这种常识你都不知道”的眼神看着我。

洛谷用的管理员都是中学生？？这不是童工吗？？

这是志愿者。

哪里来的时间？？

他们很强，肯定是保送了的，所以有时间。

哦，我懂了，他们肯定是因为自己足够优秀，不需要为升学考虑，也不需要为未来的工作考虑，所以可以把自己的时间完全投入到做洛谷的志愿者这种自己爱好的事情里面去吗？那难道chen_zhe初中就保送了清华吗？然后他后面4年都不需要学习了吗？难道他初中就把高中的常规也全部学完了？包括文科？

随便你怎么想吧。

不是，这种事情面前你们怎么这么淡定？

为什么要不淡定？现在都在打比赛，不要谈无关的事情。

我的世界观都被改变了！你们却这么淡定？

你的世界观被改变和我们有什么关系？你安静一点好不好？

我没有话说了。只能把深深的震惊吞进自己的肚子里。我怀疑自己穿越了，不然不可能会遇到这种“自己看来完全不可能发生的事情在别人看来很平常”的事情。但是穿越也是不可能的啊。

我去网上搜索“为什么洛谷的系统管理员和出题人都是高中生？”，根本没有别人问这个问题。难道我真的落后于时代了吗？

我仔细看了zhouwc的洛谷空间。他不仅是洛谷管理员，还是：

• 现任指挥使

  Incumbent commander

• 洛谷网校讲师

  Luogu online school lecturer

• 洛谷题目管理组

  Luogu problem management team

• 洛谷官方比赛出题组

  Luogu official competition design group

• 参与 55 次洛谷月赛出题

  Participated in Luogu monthly contests for 5 times

• 担任 3 个月洛谷题目管理志愿者

  Served as a volunteer in the management of the problems for 3 months

• CSGRound 创始人/组织者

  CSGRound founder/organizer

• EERound 联合创始人

  EERound cofounder

  指挥使工作职责：

  • 指挥志愿者进行题库管理。
  • 删除，封号，棕名等秩序相关。

中学生创业？？？

网络上对中学生创业的评价只有“成功率很低”。

难道现在网络的包容性已经这么大了吗？这种前无古人后无来者的事情，这种完全不符合逻辑的事情发生了，居然没有人提出质疑！没有人感到震惊！

我觉得就算我去网上问发生这种事情的原因，所得到的答案也会很不屑。甚至可能根本没有人给出答案。我放弃了。

而且我已经不敢进入CYJian周围10米的范围了。他已经是一个公众人物了，比文语乐还要可怕。以我的心理素质，根本不可能靠我自己去问这种事情的原因。

只有袁湘韬可以解释这些事情了。

md，这次的愚人节真的整个把我心态搞炸了。改题没戏了。

问了袁湘韬

他告诉我，管理员实际上要做的事情很少，比如对于CYJian来说只要每天很少的时间。chen_zhe就不知道了。

他看了zhouwc的简介后，告诉我，因为我不了解这些头衔什么意思，所以才会觉得很厉害。CSGRound和EERound不是什么公司或者网站，而是OI比赛系列，发布在洛谷上的那种。至于其他的洛谷官职，都是他自己把普通的志愿者活动写成很厉害的名字来装逼，却被我当真了。比如，所谓“网课讲师”，可能只是在某一次考试中讲解了题目，或者因为拿到了NOI金牌所以可以在某一次课程中讲一节课这样的，和学而思网校里的由有教师证的成年人担任的讲师是两个性质。

原来无知才是原罪。因为洛谷一开始是org，所以没有钱来聘请管理员，而且没有OI经验的管理员也无法应付“题面 看不懂”的问题，所以就想出了“让用户来当志愿者”的主意。而我们看到的这些洛谷比赛的组织过程不是管理员头子向下面的工作人员派发工作，然后根据反馈计算业绩这样的公司模式，而是一群管理员在一起开个qq群私信，相互安排任务这样的比较接近学生生活的形式。

至于作为luoguVIP的chen_zhe为什么从初一就是管理员，这还是一个未解之谜。可能他和蕾米莉亚是同等级的吧。算了，不要去想蕾米莉亚，不然我这个星期都会失去高兴的情感了。

0331

今天的信息学习很顺利：因为以为数论26题的比赛要结束了，而且被袁老师点名批评：“这三个人怎么做的这么慢”。正好我想着要反超，于是我就在一个晚上一连做了5道题。虽然都不难，而且我也并没有反超谁，仍然是倒数第三，但是我还是很高兴。

其他的就没什么了。明天主要要做的是补作业。

0401

愚人节真是一个奇怪的节日。

我的名字变成灰色的了。这应该是洛谷的一个玩笑。

0402

昨天晚上我没有做题，在补常规作业。

今天要多补几道题了。但是连续看了四五道题，都没有一道会做的。

我的疯狂被屠

本来以为要用矩阵做，在思考了半个小时之后得出了“矩阵快速幂不能求二次项”的结论。我觉得此题无解而上网查题解，发现这道题要用到的是斐波那契数列自己的性质！而且需要数形结合。

0403

LISA发布了三个通知：

1. 4月7日班会，要展示自己的运动、劳动、四份学习计划。
2. 明天记得默哀。
3. 英语的考试范围。注意复习时文阅读。

今天第一次做到了把所有课都上了不缺课。信息看了许多的资料，但是没有做题。我的进度已经又到了倒数第二了。

0404

这台电脑有点卡。

上午的考试（三道都是北京省选原题，可以直接搜题目标题）

机动训练

更正已完成！

预计30分，使用了暴搜。枚举每一条路径（通过枚举出发点，然后把深搜走出来的每一种路径都）并在Trie上保存每一种路径有多少种，最后把每一种路径的个数的平方和加起来。

题解：

思路基本是一样的，但是需要用DP来优化。

他没有使用Trie。事实上，他没有统计每一种路径有多少条，而是统计有多少种方案可以由两个人走出两条完全相同的路径。这个的答案和每一种路径的个数的平方和是相等的。

同样的，因为题目条件的限制，他需要规定每次出发走的是哪个方向。对于两个人需要分别规定，而且容斥是需要嵌套的。

在规定了两个人的走向之后，就可以DP了。设f[x][y][p][q]=第一个人在(x,y)，第二个人在(p,q)，两个人接下来走出相同路径的方案数。转移方程如下：

其中dx,dy,dp,dq需要根据两个人的走向来规定。

一共需要进行多次DP，但是复杂度是常数级别的。

树的难题

看到的第一眼就知道是点分治，但是我并不熟悉点分治，连模板都打不明白，所以为了让这道题发挥作用，我今天就把点分治详细地学习一遍（但是实际上并没有完成）。

题解（李思齐）：

点分治，对于每一个重心，把它的儿子节点按照颜色排序，维护两棵线段树， 一棵是与当前颜色相同的树，一棵树是与当前颜色不同的，树上维护的内容是下标为链的长度，值为满足长度为这个长度的链的最大总权值。

魔法咒语

有一些单词（总长<=100），和一些禁忌单词（总长<=100），你要用这些单词拼凑出一条长度正好为L的咒语，使得其中任意一个子串都不是禁忌单词。求方案数。

我的算法是维护两棵Trie，分别存储单词和禁忌单词，并把第二棵做成AC自动机。用dp[i][u][v]表示字符串走到第i位，第一棵Trie走到u点，第二棵AC自动机走到v点，走到这个状态的方案数。

预计60分，但是提交后是10分，我不禁怀疑我的算法的正确性。但是，经过向袁湘韬的询问，他指出了我的两个错误：第一，如果mrk[nxt[u]]>0 ，那么就也要让mrk[u]>0。这是显而易见的，和AC自动机模板的匹配过程中要沿着nxt数组回溯是一个道理。只需要在广搜时每个点u的最后一步加上mrk[u]|=mrk[nxt[u]];就可以了。第二，我忘记取模了。修改了两处错误之后就得到了60分。

袁湘韬的60分算法和我不一样。他只做了第二棵树，状态也只有dp[i][j]，表示前 i 个字符和在AC自动机上位置 是 j 。然后，每次转移时选取一个单词，然后在AC自动机上把这个单词走完，如果走完了没问题就可以向dp[i+单词的长度len][j按照单词走len步到达的位置]转移，如果走的过程中经过了被标记的点，那这个单词就不能被选。

对于后面的40分，我尝试了一些排列组合、容斥原理的做法，发现没办法解决，所以就放弃了。

题解：https://www.luogu.com.cn/problemnew/solution/P3715

这是一道对数据分类讨论的题。前60分就是这么做的。后面的40分需要用到矩阵快速幂优化转移。

我们要优化的是那个dp[i][j]的转移。 在前20分中，因为所有单词的长度都是1，所以所有的转移都是从dp[i]到dp[i+1]的。所以只要把AC自动机做成一张邻接矩阵当成用来转移的矩阵（所以矩阵的边长是100），就可以了，每乘一次就会把整个dp往后推一步，一共推L步就可以得到答案。

而对于后20分，长度为2的单词的存在使得这个方法看起来不可做了。但是实际上可以用同一个方法做出来。

首先，用这些2字母单词所能得到的AC自动机上的点的能否互相到达的关系也是可以在\(O(NM)\)时间内求出来的。然后，我们就像斐波那契数列中，在矩阵中同时保存\(F_{i-1}\)和\(F_{i-2}\)一样，我们在矩阵中同时保存两个数组：\(dp[i-1]\)和\(dp[i-2]\)。但是，不是保存成`\(2\times n\)，那样就没办法做了；应该保存成\(1\times2n\)。然后，转移矩阵就是像下面这样：

哇塞，这算法神了！

? ——鲁迅

0405

考试

lucky

我用的是指数生成函数。其他人用的是递推，用排列组合递推。

递推做法（动态规划做法）

先不考虑前导零问题，设dp[i][j]表示除了7以及一次都没有出现过的数字以外的所有数字中，使用了前i个，凑出一个长度为j的数的方案数。

递推式：

然后，运用组合恒等式把最终的答案与7结合。

对于前导零的问题，可以使用容斥原理，把所有情况减去至少有一个前导零的情况（也就是占用一个前导零来作为开头）。

指数生成函数

如果数字i出现了h[i]次，那么

如果一次都没有出现， 那么

把除了i=7以外的所有的式子都乘起来，可以得到一个多项式

而\(a_k\)就是长度为k的数的方案数。

因为7的个数太多，不能直接相乘，所以要用排列组合完成最后一步。当然，处理前导零的容斥也是要做的。这两点和标准算法几乎一模一样。

我只有10分的原因是，没有考虑到容斥的过程中，如果已经规定了有一个前导零，那么在其余的部分中是可以没有0的，但是我仍然按照数字中至少有一个来看待。所以出了错，少了90分。这种其实很明显的错误我之前完全没有察觉到，所以我也不能指望自己“以后注意”。可能做到的有一件事：这道题中0和7都是特殊元素，所以要对它们进行重点调试，也就是调试的数据要针对于可能出错的点进行所有情况的覆盖。

treasure

神仙DP题。

我只会最简单的部分。其实全班都只会最简单的部分，有的人多骗到了10分。

解法题解中讲得很清楚，不用再梳理了，唯一的讨论点事刘振西的算法中，在向下走的过程中对上一行的右边以及这一行的左边进行了扫描，向右走的时候不扫描；而题解的算法中，是在向下走时向这一行的左边扫描，向右走时向这一列的上面扫描。这两种扫描方式都能全覆盖，都是对的。

card

首先第一步要想到把卡牌分布转化成出牌序列，而且要知道每一个出牌序列都唯一对应了一个卡牌分布。

然后就是排列组合推式子了。没有什么好说的。

两日总结

昨天的考试的收获：

T1：信息学竞赛的题目最重要的事情是开头的那一点转化。那是点睛之笔，也是做题开始时应该进行枚举尝试的东西。应该枚举的是把题目条件和待求项进行各种转化，而不是尝试用各种数据结构看能不能做。

T2：点分治很重要。

T3：1. 用矩阵求快速幂的时候，初始矩阵一定只有一列，但是可以很长。2.没有发挥出完全作用的模板算法，一定要想办法用基础算法代替，不然可能会导致不好优化。

今天的考试收获：

T1：调试的数据要针对于可能出错的点进行所有情况的覆盖。

T2：做题多一点，考试顺一点。

T3：同昨天T1。同时，组合恒等式一定要完全掌握。

我居然仍然没有完成联赛数学基础。。。无颜见江东父老！

0406

组合八题

设球有n个，盒子有m个。

如果球相同，那么每一个盒子里装的一定是连续的一段。

如果盒子相同，那么最后要乘以一个\(\frac{1}{m!}\)。

球不同，盒子不同，可以为空

\(m^n\)

球相同，盒子相同，可以为空

放苹果问题。因为题目性质，苹果的放置顺序没有意义，而且只能放置在最后一个盒子中。f[i][j]表示已经放置i个苹果在j个盒子里。

f[i][j] = f[i - 1][j - 1] + f[i - 1][j];
f[1][1] = 1;
f[0][1] = 1;

就是组合数了。\(C_n^m\)。

0410

当没有人教你的时候，你就慢慢学会怎么学习了。

? ——ysuperman

现在展现在我们眼前的是云跪高原。

? ——王逾昔

今日凸显出的学习问题：

1. 欧拉函数的性质
2. 线段树分治
3. 全0矩形

学习内容：

线段树分治 （CDQ分治（三维偏序（unique双指针）））

乌合之众 mob

第一眼就想到了拆为很多位，每一位统计全1子矩阵和全0子矩阵的个数。

然后接下来半个小时都在想这个问题，但是我忘记了最大全0子矩阵的单调栈做法，而弦线法无法解决计数问题。

最后把O(N^3logN)的算法打上去了，没想到居然爆零了。不知道为什么。

正解：

使用单调栈。首先枚举矩阵下界，然后枚举右下角。通过维护保存高度的单调栈，维护该右下角的矩阵可能够到的区域面积S，而面积大小就是方案数。

已经更正完成！

圣战 crusade

此题的解法相当麻烦。主要任务就是找出所有边，使得它被所有奇环包含，而且不被任意一个偶环包含。

显然是要得到一个生成树，然后进行树上差分。难点在于算法正确性的证明。

另一个做法是，用线段树分治做。

花火之声不闻于耳 hanabi

这标题一看就是老辉夜厨了。

一个欧拉函数题。一开始我做不出来，以为是没有了解全部的欧拉函数的性质，但是后来讲题才知道只是我把路走窄了。

我想着对任意两个数x,y，由\(\phi(x),\phi(y)\)得到\(\phi(x,y)\)的公式，结果因为gcd没法维护把我自己整晕了。

但是实际上这道题是要按照学过的公式来做。

法一

300以内的质数有62个。开62棵线段树（注意空间），每一个线段树中维护每一个\(a_i\)中包含质数\(p\)的次数。

对于一个质数p，显然有\(\phi(p^k)=(p-1)p^{k-1}\)，可以\(O(log k)\)求出来，查询时只要在每一棵线段树中把那个区间内的所有\(\phi(p^k)\)求出来，再把这\(62(R-L+1)\)个函数值全部乘在一起得到答案。

法二

因为有公式\(\phi(x) = x\prod \frac{p-1}{p}\)，我们分两个线段树来维护这个答案，一个维护x， 一个维护\(\prod \frac{p-1}{p}\)。前面一个不用说，后面一个线段树因为只需要维护每一个质数存不存在就可以了，所以不用开62棵，只需要开一棵，并用long long进行状压。

0411

树链剖分 decomposition

这道题看起来非常简单，导致我没有多想就写成了子树修改。但是实际上，新的修改是可能不能影响到它的某些子树的。这件事看起来非常麻烦，然而又许多的解法。

法一

在线段树的每个节点处记录该部分被遍历到的所有时候中，x最深的一次操作是多深。那么，如果是没那么深的点x的操作遍历到了这里，就说明x肯定就是那个最深的点的祖先，那么这次修改就不能进行。

因为线段树常数太大所以很难得到100分。

法二

不用线段树。离线操作，把所有操作做完之后反过来，标记点的操作变成擦除点。

维护一个并查集，每个点连到它的金丹的来源。当一个点被擦除后，就把它合并到它在树上的父亲的集合里。

要带权，权值就是金丹的来源。这样才能启发式合并。

法三

张明驰想出来的方法：把时间视为一个独立的维度。

首先保存每一个点被标记是在什么时候。 并维护一个数组b，下标为时间，值为该次操作的点的编号（而且只保存修改操作），但是一开始不要存这个值，而是保持为0。

在树上深搜，当进入一个点u的时候，就把这个点激活，也就是把该点编号存到数组b中相应的位置去。当离开一个点u的时候，就把这个点关闭，也就是把数组b中相应的位置归0。 显然，被激活的所有点都在当前位置u到根节点的一条链上。

在进入点u的时候还要处理每一次对u的查找。显而易见，影响一次查找u的，只有修改时间在该次查找之前的修改操作；而且这次查找的真正答案是这些修改操作中（同时满足修改位置在u到根节点的链上），点的深度最深的那次。那么，就只要把数组b中，时间在1~time[u]的，被激活了的修改操作中，找出深度的最大值是哪一个。这件事可以用树状数组实现。

总结一下：每次询问的答案的限制中，有一个维度（时间）被作为偏序限制（所以用数组的下标区间解决），一个维度（是否在链上）被作为限制因素（灵活运用深搜的性质），还有一个最优化条件（最深）（所以需要树状数组）。真是妙啊！

天气之子 tenki

这是一道数学题。

我通过找规律，加上小心翼翼的高精度调试，成功拿到了100分。

我自认为不严谨的证明，居然就是正解的证明。

层层染君色 mafumafu

这道题的大概思路我都是对的，但是许多细节出了错。

第一件事就是求\(\sum_{i=1}^n i^k\)的值。如果用枚举+快速幂，\(O(D\ \log D)\)的时间有点紧张，可能会少一些分数。但是我以为这个问题只能通过卡常解决，但是在考完后讨论的时候被人一句“线性筛”点醒：用线性筛，那么只有素数的\(p^k\)需要用快速幂算，别的都是线性的。因为素数只有\(\frac{n}{\ln n}\)个，所以整个的时间变成了\(O(n)\)。太妙了！

听李思齐说， 如果n有\(10^{15}\)级别，那么就需要使用拉格朗日插值来做。具体的内容，可以在拉格朗日插值的模板题的题解中查看。

然后，就是线段树维护的是什么的问题。我只维护了每个点子树中黑点的个数bsz，然后通过乘每一个点的系数。没有细想这其中隐藏的问题。区间查找的时候，如果一个点的孩子被修改了，在查找的时候却只找到了这个点，那么那次修改就被忽略了；而如果直接把bsz加上来，那么就会导致部分的bsz乘上了这个点总体的系数。这个矛盾是无法调和的，所以必须修改维护的对象。

如果维护的是乘上了系数之后的值，就会发现这个很好维护。因为查找的就是乘上了系数的值之和，而修改的内容也很容易就可以转化为乘上了系数的值，所以这种算法就没有内部的矛盾。

另外一个问题就是，我居然把欧拉线性筛写在了k的输入的前面！！！怪不得答案相差那么多。

已经改对了。

类似的题： 洛谷P5305

其他

1. 省选竟然只有8MB的栈空间，也就是说图论和树论的DFS要用非递归版本或者BFS代替。我还得找高二的确认情况。据说至少去年是这样。
2. 老师强制我们使用Linux。今天再次引发了一场我适应Linux的讨论。结果是好像我的所有问题都是可以解决的。但是往常和这次一样，开始使用前忘记了当时遇到的所有问题，一开机，20分钟之内就让我体验到什么是绝望。
3. zzt说没必要了解Ubuntu Linux的底层架构，包括home文件夹的位置，怎么通过cd进入U盘之类的这种东西。他在不知道的情况下都能够做到安装系统这样的事情，我就没必要深究了。只要学习Linux的快捷键就可以了。
4. 今天就要决定是否要停课了。在情报不足的情况下根本没法做决定啊！我要学会怎么在这种情况下做决定。两边都很难抉择，而且我更偏向于不停课，但母亲说要停。我们还没有正面讨论过。

《飘雪》从前天晚上开始就拯救了我。

0412

难道Linux是强行让整个系统中的所有字体都统一吗......为什么连Typora中的News print主题用的都是这种充满了代码气味的字体？

今天上午的任务：完成寒假的评价和省选前的计划。改出六道题（首先改昨天的第一题）。适应Linux（可以通过失去适应法）。

0416

今天的开学考试完成了。

Typora好像没有能力在学校的电脑上浏览这种超大的文件。简单来说就是优化做得不够。这个markdown文件超大不是因为什么图片之类，而是因为光是文字就确确实实有189KB（截至20200416），源代码有3400行。所以在学校里就只能用VSCode来写了。也还不错，因为长期的使用已经给了我用眼睛预览Markdown的能力了...但是数学公式还是不行啊！

小Y的绝对战争

对于这种gcd的题目，要经常从枚举gcd的值，再求满足这个gcd的方案个数的角度切入。

我的错误原因是没有想清楚在多个点的权值相同时怎么计数的问题。因为在小数据中没有两个数相等，所以出现了小数据没问题而大数据WA的情况。这让我还以为是数组开小了的原因。想必以前的类似问题肯定也是这样，我的算法本身是错误的，但是由于小的数据范围不易出现某种特殊情况所以就显示为小的数据结构全部AC的情况，让人以为是数据范围导致的错误。

Miller Rabbin 素数测试

这个算法比我想象中的容易很多。

当p为质数时，由费马小定理有：\(a^{p-1}\equiv 1 (mod\ p)\)。所以只要随机枚举几个a，看看是否符合这个等式，如果不符合就说明p不是质数。

但是，费马小定理的逆定理不一定成立。有的数，尽管不是质数，仍然对于所有的a都满足那个公式。我们可以加上另一层条件，来筛除这些内容。因为p一般是奇数，所以p-1是偶数。那么就可以有这样的操作：

因为p是一个质数，所以\((a^{\frac{p-1}{2}}-1)\)和\((a^{\frac{p-1}{2}}+1)\)中必然有一项整除p，但是合数的话就不一定了。如果不符合上面这个条件的，也不能通过测试。

对于选取的a，根据经验，只需要5个：2, 3, 7, 61, 24251。但是，就算这样，仍然有例外：46856248255981。它不是质数。另外，这5个用于判定的素数在作为n输入时，也要特判。

博客链接

0417

明天早上7:40开考。有点麻烦。7:30之前到机房。

YY的GCD

以前没有正儿八经地做过莫反的题目。今天开了眼界，会莫反和会莫反的题目是两件事。

首先，用莫反来快速解决\(\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=d]\)的问题，可以三步解决，还可以转化状态。我要明白的一个重点问题是：莫反的第二式中，\(F(x)=\sum_{x|d}f(d)\)d可以达到无穷大的原因：一般这种地方的\(f(d)\)在d达到一定大小之后就都等于0了。

另外，我还想要证明这个定理：

经过向张明驰求证这个定理的正确性，并花费5分钟进行尝试之后，这个定理被证明了。这真是太好了。

其他

为什么开学后在机房的晚自习的时间过得那么快？每天晚上都做不了什么。相比前两天准备月考的时候，每天晚上学习的常规内容的信息量是成吨的，在机房每天晚上能学的东西几乎和羽毛一样轻，都没什么东西。做题不超过一道，往往是看完两篇博客，推了几个式子，两个小时就过去了。这种多年未发生过的现象令我很迷茫。上次出现这种时间飞速流逝的感觉还是初二时在家里写代码的时候。

0418

今天的题目是三道码农级别的题目。两道点分治一道LCT。我醉了。

树 Tree

图 mincost

危机 crisis

今天我没有想着去改题，因为根本没有能力。我叫上了刘振西，尝试去解决在LCT中遇到的细节问题，把整个数据结构整理清楚。最后，进展很大，但是仍然没有看懂关于pushdown的部分。pushdown是最后的难点了，我保证。胜利在望。

点分治至少要打个模板题吧！我听他们讲点分治的题讲了这么多遍，我自己对这个算法都熟悉了。

0419

能量采集

刚刚来到这道题的时候，我怀抱着对莫反的敬意。但是转头一看，我居然已经AC了这道题，但是我记得我并没有做过莫反的题啊？于是我就跑去看，发现我当时用了一个十分简便的做法。没有使用莫反，而是普通的反演：

这样，只要保存了所有的f[]，就可以用\(O(N\ln N)\)的时间求出所有的f。这种算法与莫反是完全无关的，但是用的场合又几乎相同，而且算起来、写起来都简单很多，不过时间复杂度多了一个\(\ln\)，而且也没办法用整除分块的方法来处理多组数据的题目。

YY的GCD

在lsq把课上了之后，我把许多关于莫反的细节都整理出来了，真正弄懂了这个东西。再次看这道题，觉得难度没有前天看的时候那么大了。

在这个题的下面我发现了一个和能量采集的简单做法有异曲同工之妙的解法，也是通过那种简单的反演求出所有的f[]。

还有一个神仙解法，用线性筛求\(f(x)=\sum_{p\in prime,p|x}\mu(\frac{x}{p})\)。做法就是列出一个递推式，包括三种情况：\(x\in prime,x\%j=0,x\%j\ne 0\)。对于这三种情况的递推式进行分析，得到一个可靠的递推式。

这真是一个宝藏题目啊。

0420

今天要交做题记录。而且突然说要记录每次考试的题目，我很震惊。

以前的考试的题目（就是开学前的连续两次的考试）确实还没有改完，一些照着AC代码抄都没法AC的题，还有一道点分治。

怎么这么多点分治啊！导致我欠了很多题的更正。

昨天的讲课内容因为公式太多，而且上课时控制了屏幕，所以在纸上做了笔记，没有电子笔记。

我刚才在没有完整看完题解的情况下自己推出了YY的GCD的那个欧拉递推式，真是太爽了！

明天找时间学LCT。必须白天做完作业，才能在晚上把LCT攻克。

0422

今天作业不多，居然能在八点之前写完，没有想象中会面临的那种麻烦事。

YY的GCD

今天终于把这道题改出来了。原来是因为再一次忘记了isnprime[i * prime[j]] = true;，再次喧宾夺主。

BSGS

P2485 计算器

这道题最坑的一点是输入的y没有\(y的限制，导致y完全有可能成为p的倍数，导致第2、3问无解。要是这里的无解没有考虑到，就只有55分。

写得还算顺利，自己用链式前向星写了一个Hash，感觉良好。

exBSGS

0423 ABS讲课

计算几何

好像计算几何的灵魂就是向量。

基础

向量加减、数乘、点积、叉积。两个向量的夹角的cos和sin值。极角排序（先按照象限再按照叉积）。

向量旋转

将向量\((x_1,y_1)\)向逆时针转动一个角度\(\theta\)，得到的新向量为\((x_1\cos\theta-y_1\sin\theta, x1\sin\theta+y1\cos\theta)\)。用和角公式可以证明。

向量投影

将向量\(\vec{a}\)投影到\(\vec{b}\)上的答案为\(\frac{\vec a \cdot \vec b}{\vec b ^2}\vec b\)。

直线

用两个向量\(\vec p\)和\(\vec v\)表示：\(l=\{\vec x |\vec x=\vec p+t\vec v\}\)。

直线交点

两条直线为\(l_1:(\vec{p_1},\vec{v_1}),l_2:(\vec{p_2}, \vec{v_2})\)。因为交点在\(l_1\)上，所以设交点为\(\vec{o}=\vec{p_1}+t\vec{v_1}\)

解得：

代入原式就可以了。

线段求交

不需要求所在直线的交点！不需要求所在直线的交点！不需要求所在直线的交点！

已知两条线段的四个端点：\(l_1为(\vec{s_1},\vec{t_1}),l_2为(\vec{s_2},\vec{t_2})\)。这两个线段有公共点当且仅当

这其中只有一个特例：当两条线段没有交集但是在同一条直线上的时候，这个式子会把它们判定为交集。解决这个问题只需要在这条判定之前，加上这样一条判定：

两条线段分别形成一个外接矩形（矩形的长宽与坐标轴平行），如果矩形没有交集，那么两条线段一定没有交集。

这同时还可以把大多数的线段之间的关系给判为不相交，避免了后面的四次叉乘，是一个很好的常数优化。

点到直线垂足

同样是用解方程来解决。设点为\(\vec q\)。

得到

点到直线距离

利用叉积。

求两个向量的角平分线

有两个方法：等腰三角形的中线，和旋转一半的角度。后者比前者好，因为当两个向量的夹角非常接近\(2\pi\)时，这个等腰三角形也会非常扁，使得求中线时，一点点的位置误差就会导致很大的角度偏移。

求一个向量在一条直线上光的反射

旋转角度，没什么好说的。

多边形三角剖分

有向剖分：逆时针枚举每一条边\((\vec u, \vec v)\)，原点与这两个端点构成一个三角形。所有的这些三角形就是对这个多边形的三角剖分，所有的\(\vec u\times \vec v\)之和就是这个多边形的面积。

无向剖分：每次削掉一个凸出来的角。很麻烦而且没有什么应用场景。

用有向剖分可以求多边形重心。

判定点是否在多边形内

首先判定是否在多边形上。

设这个点为Q。让一个点P在多边形上绕一圈。如果\(\vec{QP}\)累计旋转了\(2\pi\)或者\(-2\pi\)，那么Q就在多边形内。如果累计旋转的角度为0，那么Q就在多边形外。

另外有一些做法，比如从Q点发射一条射线，如果与奇数条多边形边相交，Q就在多边形内；如果与偶数条相交，Q就在多边形外。但是，这个方法有正好经过顶点的麻烦，这种时候换一个角度再判定一次就好了，但是就麻烦一些了。

求一个点到一个圆的两条切线和两个切点

用巧妙优美的方法通常不适用于信息竞赛，因为通常会导致误差被放大。

最好的方法就是最笨的方法：用勾股定理算出切线长，用反三角函数求出角度，然后用旋转与缩放得到切线向量和切点坐标。

求两圆的四条切线

求线圆交点

用垂径定理。因为误差的存在，要特判相切的情况。

求圆圆交点

仍然还是笨办法。略。

三点定圆

用两条中垂线相交它不香吗？不香。因为误差。

解方程才是最好的。

计算几何应用三兄贵

凸包、旋转卡(qia)壳(qiao)、半平面交。

最难的是第三个。

反三角函数

晚上的Imakf copies III比赛

比赛在CF上，网络很慢，还经常连接超时。Imakf告诉我一个CF的镜像网站：codeforces.ml。稳定了一些，但是还是经常连接超时。

Imakf告诉我题目不是按照难度排序的，所以我先浏览了所有题目：一共有9道，居然只给两个小时？我先挑了看起来最简单的A+B，没想到居然真的就是最简单的，真的就是A+B，而且值域是100。于是我就做了第一题。

然后，看standings，看到袁湘韬已经做出了第二题：Cards。这通常是一次考试中最恐怖的题目的名字，但是我还是点进去看了。是一道水题，太好了。我就做了。

然后再次看到standings，袁湘韬做出了第三题：Guess the Number。这是一道交互题，二分答案猜数字。没什么难度。当我做完这道题时，时间过去了29分钟。主要原因是网站太慢了，总是连不上。

然后再次看到standings，袁湘韬做出了第四题：Multiplication Table。我也跟着看这道题，不是水题。但是很快也可以找到解法，就是对于每3个数。可以把乘法表上它们的三个两两乘积都乘起来，再开根号后，除以三个乘积中的任意一个就可以得到这个乘积中没有涉及到的那个数的值。难点在于三个数乘起来达到了\(10^{27}\)。在质因数分解和用long double两个方法之间纠结发现无法质因数分解之后，就选择了long double。通过尝试，发现了最大的误差0.03，于是就解决了误差问题。这是棒啊！于是这道题又在没有什么压力的情况下解决了。这时时间过去了56分钟。

然后再次看到standings，袁湘韬做出了第五题：Substring Game in the Lesson。这是一道博弈论题。通过紧张的分析，我得到了一个写起来很简单的算法。写完提交居然直接AC了。此时时间是79分钟。

然后再次看到standings，袁湘韬并没有做出第六题。于是我就开始乱看，一点点开了H题：Crossing Line。这居然是一道裸的计算几何题，考察的内容就是今天学的内容！我欣喜欲狂，立马开始码代码。40分钟后眼看着时间结束，我的代码还有这样那样的bug，突然瞟到刚刚刷新的排行榜，发现剩余时间突然变成了41分钟，我就知道了Imakf因为某种原因把时间延长了。这时我更高兴了，连忙埋头回到代码中改bug。这是一道会卡常数的题，我在写完之后生成了最大数据，测试用时两秒多，而给出的时间只有1秒。于是我又进入了漫长的卡常之旅，通过一些我自己以前试都没试过（不过可以确定是正确的）卡常技巧，把时间卡到了大约1.3秒。因为没有开O2，而且我用的是学校的老爷机，我期盼着可以在上面通过时间。提交后，我等了一分钟，得到了AC的大好消息：717毫秒！

2分钟后比赛结束了，袁湘韬以7道题的成绩得到第一名，我因为前面每道题都是一遍过，而最后一题因为忘记删freopen提交了2次，所以罚时很少，超过了另一个通过了6道题的Imakf，居然得到了第二名。张明驰看到我过了H题后很震惊，说“这道题设计出来就是不让你们过的！”但是他们过的题目我又不会，只能来解决这种码农题了。

真是高兴啊。果然我还是比较擅长计算几何，比较擅长写较长的代码。DP和数据结构是我的弱项。

0425

今天是NOI Online第二试。

color

这道题是一道数学题。还好。假设\(p_1。

以两个\(p_1\)和\(p_2\)的共同倍数之间的区间为一个单位。这中间（不包括两端）一共会有\(\frac{lcm(p_1,p_2)}{p_1}-1\)个 \(p_1\)的倍数。它们会被\(\frac{lcm(p_1,p_2)}{p_2}-1\)个\(p_2\)的倍数分成\(\frac{lcm(p_1,p_2)}{p_2}\)个部分，每个部分的个数会尽量平分，个数差不会大于1。所以就可以得到最长的连续\(p_1\)个数。和k比较就可以了。

sequence

我只会暴力。

实际上，这道题并不需要什么高级算法。陈亮恺举了一个样例，把每一个区间的答案列出来，发现了规律，然后就可以用线段树解决问题。

线段树维护的是函数值的区间和而不是函数值的平方区间和。l=1时的平方区间和可以\(O(N)\)算出，后面就只要把该减去的减去就可以了，不需要维护平方和本身。

match

这是一道超纲题。

首先用怎么想都想不到的dp做：

dp[i][j]表示i的子树中有j对产生贡献的点对的方案数。

然后就有了转移：

在i号点不加入的时候：

在i号点加入的时候：用A[i]表示i的子树中小A的点的个数，用b[i]表示小B的点的个数。

在树形DP结束之后，用到了一个叫做二项式反演的东西：

设答案\(H(k)=\)正好k对造成贡献的点对的方案数。

我们需要一个反演的\(G(i)\)满足：

袁湘韬设的是：

这个转化有点看不懂了。

其他

今天下午李思齐又做了一道我没见过的题。不知道我没见到的还有几题。差距就是这样产生的。

0426

刚来时看到很多人都已经到了，但是我是在校门刚开的13:40的时候就进来了的。我问他们是什么时候进来的，lsq说整个上午都在了这里。“本来就不应该放假啊。”

两年前的事情再次出现了。能够在学习的时候无视任何休息的需要的人，只有一种，就是热爱学习而且善于学习的人，因为这些人可以把学习本身当作休息。当时这种人在奥数班上环绕着我，让我心惊胆战了一年多，直到直升后和他们待在一个班上，才发现这些同学也是有血有肉的人。

还有一种可能，那就是他确实很努力，为了省选奋斗。但是这种情况下不可能用这么理所当然的、让人胆寒的语气说话。

如果还有其他的可能，那就是我的未知领域了。

后来我用别的东西分散注意力，十分钟后就没有那么害怕了。我就知道，对待可怕的同学，努力无视是最好的选择。

FFT讲完的感想

听完后的感觉是，本来会FFT的，现在不会了。

但是，当老师问“有谁听懂了”的时候，全体齐刷刷地举起了手。我没有。

我一个学过了的都听得不懂了，大家零基础居然能在两个小时之内把傅里叶变换的原理搞清楚？

真就人均天才啊？？

后来我了解到，很多人在寒假时早就自学完毕了。

“不会看不懂吗？”“为什么要看懂？知道怎么做就可以了啊。”“不看懂怎么知道怎么做？”“看代码啊。”“哦。”

? ——刘ZX

主要原因就是ABS的讲课真的与网上的博客和不屑的PPT很像，有很多的歧义和定义重名，只是好像句子成分的省略出现得很少。最大的一点误解是对于多项式\(f\)，\(f(k)\)表示的意思居然是\(k\)次项的系数！我问袁湘韬这难道不会导致歧义吗，他说，多项式把x代入求值的做法是很少见的，对于多项式这个通常表示的都是k次项系数。但是今天整个FFT讲的不就是快速求多项式的快速求值吗？他眯着眼睛盯着黑板，30秒后对我说，好吧，但是确实大多数时候表示的都是系数。

大多数时候？？那就是说我在遇到这个记号的时候还要分类讨论他说的是什么了？

但是在这之后不管我怎么指出我认为的这种表示方法的不妥之处，袁湘韬都再没有说出什么有意义的话了，许多时候都是眯着眼睛看着我，笑一笑。这一刻，我觉得自己像个猴子被耍了。但是，我的这个问题仍然没有解决，整个晚自习仍然需要把袁湘韬亲自请来询问这个\(f(x)\)和那个\(f_x\)指的是什么意思。这两个符号在PPT中的使用已经严重混乱了，两个符号分别都代表过函数值和系数两个意义。难道安博施会写出这样的PPT？我敢打赌这肯定不是他自己写的。

我真的输了。在说话这件事上，我输给了这个机房的所有人。可能这就像化学的学习，久了就能够看明白那看似毫无道理的几个选项其中的道理了吧，现在强求不得一时就能与大家同步。

FFT

音频

本身傅里叶变换的发明，是与音频有关的。目前能让人看懂的解释只有bilibili@3Blue1Brown的解释视频。

一段声音可以由多个单纯的声音合成。每一个单纯的声音就是一个\(A\cos(\omega x+\phi)\)。

而FFT的作用，就是把一个由多个声音混合在一起而得到的一段声音分解开。解释非常麻烦，还是要看视频。链接

最终要记得的是一个式子：

这时，\(F(\omega)\)表示的是在声音波\(f(x)\)中，频率为\(\omega\)的cos波的强度。

逆变换

袁老师：用矩阵的思想，就可以不用使用zzsPPT上的那个超级复杂的数学证明解法。

其实就是求下列矩阵的逆矩阵：

答案是：

多项式乘法的傅里叶变换

经过我仔细的思考，得到的初步结论是：多项式乘法的傅里叶变换和音频的傅里叶变换，并没有本质上的任何联系，只是因为式子的形态相似，所以可以用相同的办法优化。

FFT算法

今天的讲课和zzs的相比的区别是：今天的更偏原理一些。但是实际上这些原理对理解FFT算法并没有什么帮助。最终还是要回到那个分治的思想中去，然而在PPT中这个被一张幻灯片就简单地讲完了。

幸好我上过周老师的课。太幸运了。

好在，NTT的讲解还是比较详细的。

NTT

原根\(g\)需要满足：当\(k\)取遍\([0,P-1]\)中的所有值时，\(g^k\)也正好取遍\([0,P-1]\)中的所有值。

将模数P表示为\(P=c\times2^k+1\)，那么我们就需要选择一个k尽量大的P，来容纳更大规模的多项式乘法。它最大能处理的多项式次数为\(2^k\)。

在FFT中的\(\omega_n\)，在NTT中就相应地表示为：\(g^{\frac{P-1}{n}}\)。

求原根

首先枚举g，然后枚举\(k\in[0,P-1]\)进行验证。\(O(P^2)\)。

怎么优化？首先，原根g一般都很小，不会超过20。所以大概率可以视之为是\(O(20P)\)。

另外，g为原根，当且仅当，对任意\(k\ne P-1\)，都有\(g^k\ne1\)。

而可以证明的是，如果有\(k\ne P-1\)满足\(g^k=1\)，那么就肯定有\(k|P-1且k\ne P-1\)满足\(g^k=1\)。所以，要验证g的正确性，需要枚举的k只包括P-1的因数而已。这个的复杂度是\(O(\sqrt P)\)的。

那么这样时间就不会超过1秒了！

0502

今天有考试。

分数是100，但是本来可以有130的，因为有道题没有写freopen。

shopping

预计分数：100 实际分数：80 改后分数：100

比较简单的组合数学题。限制上限的部分不能直接容斥，然后发现dp可以很容易地解决。

剩下的就是组合数了。但是，我忘记考虑n=m的情况了，少了20分。

highway

预计分数：30 实际分数：0（freopen）->30 改后分数：100

写的暴力。

本来想过用线段树，但是发现pushup只能用暴力方法，没有细想就放弃了这个方法。实际上，还是有很多的线段树的时间因为pushup和pushdown需要时间而不是n log n的，我要有更广泛的视野。

袁湘韬用ST表+分块达到了相同甚至更快的效果。

sailing

预计分数：30 实际分数：20 改后分数：

我怎么都不会想到这是一道神仙多项式FFT题...

60分算法也很值得参考：通过前缀和和差分，可以快速判定一个矩形内有没有障碍物，也可以一次性把一个矩形内的所有点都标记。通过这种方式，求出舰队矩形的位置、长宽，广搜一遍就可以得到答案。

100分：把矩形地图展开成一个序列，就是把每一行取出来依次排在同一行上形成一个序列，所有障碍物标1，其他格子标0。用一个最小的矩形覆盖所有的船，再把这个矩形展开，船标1，其他格子标0，但是如果每一行的长度小于m，就要用0填充。

那么，你可以把地图序列固定，让船序列在地图序列上滑动，这就枚举了所有的船的可能位置。一个可能位置合法的条件是对于任意一个位置，两个序列都不同时为1。统计这样的合法方案有多少的方法就是：把船序列倒序，拿它和原序列卷积，得到的答案中，哪些位上为0，就说明这些位所表示的方案是合法的。

但是，光是知道了合法方案，还是不能在时间内求出合法方案啊？这时就需要另一个卷积了。用“在展开序列中最靠前的那艘船”作为每一组合法方案的位置，然后把地图序列展开，每一个合法位置标1，其他格子标0，然后和船序列卷积。这样，卷积得到的答案中，只要是有船去过的地方，该处系数就会大于0。扫一遍得到点的个数就可以了。

需要FFT。

0503

考试策略

先看完了所有的题，然后决定做哪道。

经验和教训

第一题：(互质数组)

期望得分： 100 实际得分：100 改后得分：100

解题思路

相邻元素判断是否互质。考场上人均100分。

失分原因

解决办法

第二题：(线段)

期望得分：60 实际得分：0（60） 改后得分：100

解题思路

30分用暴力，30分用坐标系内前缀和。

正解：把区间按右端点排序，用树状数组统计每一个左端点有多少个区间。

失分原因

没关调试。实际上确实是60分。

解决办法

多做题。这种经典、无知识点的套路题，需要靠熟悉来凑。我清楚地记得自己做过这类型的题，但是忘记了具体怎么做。

第三题：(选择元素)

期望得分： 100 实际得分：20 改后得分：100

解题思路

用了欧拉线性筛，用\(f(t)\)表示当lcm为 t 时序列内有多少个数是t的因数。虽然这\(f(t)\)个数的lcm可能小于t，但是最优解肯定没有这个问题。然后就写了欧拉线性筛的递推式。考场上的递推式已经被证明是错的了，但是后来改对之后仍然是WA的。

好像没有其他人想到用这个办法，所以正确性也无从考证了。

而正解根本没有想这么多，直接一个调和级数的写法，简简单单就把我踩了。

失分原因

没有冷静思考。这是我做的最后一道题，时间不多了。

解决办法

。。。不知道。

第四题：(树)

期望得分：30 实际得分：40 改后得分：

解题思路

就是骗分。前10分乱搞，完全没有预料到居然对了；10~40分因为是链状的树，所以可以像序列一样处理。没有想象中的那么麻烦。

我是想过用二分答案的，但是放弃了，因为不知道怎么处理深搜的问题。实际上，这道题需要把深搜的性质提取出来：如果不把一棵树搜完就不会离开这个子树。所以如果这棵子树中有被不合法化的点，那么就不可能再从其中出来。设dp[x]为x的子树最多能走多少步，如果dp[x]==size[x]那么就说明可以从里面走出来。转移就是：

int Manacher() {
    int r = 0, mid = 0, ans = 1;
    p[0] = 1;
    F(i, 1, len - 1) {
        if(i <= r) p[i] = min(r - i + 1, p[(mid << 1) - i]);
        while(s[i + p[i]] == s[i - p[i]]) ++p[i];
        if(p[i] > ans) ans = p[i] - 1; // 此代码求的是最长回文串
        if(i + p[i] - 1 > r) { r = i + p[i] - 1; mid = i; }
    }
    return ans;
}

输入的数组：ABABAB
原来会修改为：#A#B#A#B#A#B#
现在修改为：!#A#B#A#B#A#B#

// P4124 题意：求[L,R]之间，有多少个数满足，出现了连续3个相同的数，而且不同时包含8和4.
const ll N = 20;
ll L, R;
ll dp[N][4][11][2][2];
ll x[N];
    //还剩pos位，是否是上限状态，已经连续了多少个数，上一个数是多少，是否出现了4，是否出现了8
ll dfs(ll pos, bool lim, ll r, ll lst, bool i4, bool i8) {
    if(i4 && i8) return 0ll;
    if(pos == 0) {
        return r == 3 && (!i4 || !i8) ? 1ll : 0ll;
    } else if(!lim && dp[pos][r][lst][i4][i8] > -1)
        return dp[pos][r][lst][i4][i8];

    ll up = lim ? x[pos] : 9;
    ll down = lst == 10 ? 1 : 0; // 控制前导0。这道题里不能出现前导零。如果可以出现前导零，那么这个down就值为0，而前导零和普通零也不需要区分了。
    ll ret = 0;
    F(i, down, up) {
        ret += dfs(pos - 1, 
                   lim && i == x[pos], 
                   r == 3 ? 3 : (lst == i ? r + 1 : 1), 
                   i, 
                   i4 | (i == 4), 
                   i8 | (i == 8)
                  );
    }

    if(!lim) dp[pos][r][lst][i4][i8] = ret;
    return ret;
}

ll getans(ll val) {
    ll len = 0;
    for(; val > 0; val /= 10) {
        x[++len] = val % 10;
    }
    if(len != 11) return 0; // 这句话是因为P4124数据有误
    ll ans = dfs(len, true, 0, 10, false, false);
    // pr("%lld\n", ans);
    return ans;
}

int main() {
    clr(dp, -1);
    L = rd(); R = rd();
    pr("%lld\n", getans(R) - getans(L - 1));
    return 0;
}

dp[u][l][0/1] = 以u为根节点，链的长度为l，能否往上走，在此子树中的最小偏心距。