CodeChef LTIME23
首先得声明一下，这套题不全是我自己做的，第二题是lzw帮忙做的。因为lzw那边突然无法登入CC，会直接转入一个wpkg.org的网址（现在，我的电脑上也出现了这种情况），所以他提议和我一起做这场CC，然后，由他来解决T2（因为在他电脑出状况之前，他T2已经做得差不多了），所以最后，T2是lzw做出来的。
虽然是两人联手，结果由于我在关键时刻掉链子，最后没有AK，有点郁闷。
Problem A-TICKETS5
开始做这道题的时候，还没有中文题面，然后，因为本人英语渣，看错了题，放过了单词alternate（这个词是交替的意思），以为只要字符串出现的字符只有两种就行了，然后竟然AC了（我可以吐槽数据吗），后来才发现，两种不一样的字符竟然需要交替出现。
Problem B-HCLEAN
这道题是lzw做的，我没仔细看，现在大致说一下我的想法，当D<4的时候，肯定是不行的，因为不可能存在边，当D$\geqslant$4的时候，至少两两顶点之间是可以连的，因为是n维正方体，肯定是存在一条哈密顿路的。于是，我们可以直接构造出一种方案（构成一个环），然后再找到输入数据要求的那个顶点所在的位置，最后从这里开始输出就行了。那该如何构造呢？我们还能发现，n维坐标，每位要么是1，要么是-1，和二进制数非常相似。接着，我们又想起来（其实我是经过lzw提醒才想到这东西的），有种东西叫做格雷码，要求相邻两个数只有一个二进制位是不一样的，所以，我们就先求出格雷码，最后找到起点开始输出就行了。
Problem C-XETF
这题最开始的时候，题目看错了，以为是求出所有非n约数的数的K次方之和，坑了一个多小时之后，眼看就要解决了，突然发现题目看错了，真是欲哭无泪。然后赶紧补救，结果因为时间问题，没能搞完。最后还少拿了28分，真是可惜。第三部分数据的公式都已经推出来了，结果后来由于乘起来爆了long long，一直WA，然后我就以为是公式（最开始的公式是Claris给我的），可是自己手推公式又没有多少时间了。下面讲一下做法。
subtask1就是暴力+快速幂，相信大家应该都会。subtask2直接就是$\varphi(n)$，估计大家也应该都会。subtask3的公式是$\frac{n*\varphi(n)}{2}$，对于大于2的数n，$\varphi(n)$是偶数，所以这个公式的结果永远都是整数。唯一要注意的是，n和$\varphi(n)$乘起来会爆long long，所以要先取模再乘，然后再乘以2的逆元就行了。公式的推导过程也给出来吧：$$A_{1}+A_2+...+A_{\varphi(n)}=\sum_{i=1}^{n}i*[gcd(i,n)=1]=\sum_{i=1}^{n}i*\sum_{d|i,d|n}\mu(d)=\sum_{d|n}\mu(d)*\frac{\left( \frac{n}{d}+1\right)*n}{2}$$
$$= \frac{n}{2}*\left(\sum_{d|n}\mu(d)*\frac{n}{d}+\sum_{d|n}\mu(d)\right)=\frac{n}{2}*(\varphi(n)+\left[n=1\right])$$
subtask4的公式其实我们也是推出来了的，感觉实现起来比较麻烦，然后就没搞（主要原因还是时间来不及了），我们推出来的最后的答案是$\sum_{d|n}\mu(d)*d^k*S_k\left(\frac{n}{d}\right)$，其中$S_k(n)=\sum_{i=1}^{n}i^k$，主要的复杂度在于求$S_k(n)$，杜教有一份课件，叫做多项式与求和，里面给出了各种做法，最快好像能做到$O(k)$？如果感兴趣的话可以去看一下。
Problem D-PALPROB
这道题我竟然是第一个AC的，真是高兴。这道题要求出所有的回文串的出现次数，这当然要用回文树了，直接扒了模板过来。然后，就有点讨厌了，要求回文值，回文串S的回文值是S前$\lfloor \frac{|S|}{2}\rfloor$的字符组成的字符串的回文值+1，字符的回文值为1。回文树的构造过程中，有种东西叫做后缀链，指向的是当前回文串的最长回文后缀。既然一个字符串是回文串，那么前一半和后一半应该是反过来的，但是，这并没有影响，因为后一半的回文值>0当且仅当后一半也是回文串，那么在这种情况下，S的前一半和后一半就是相同的了。我开始的时候怀着侥幸的心理打了一个暴力，沿着后缀链走，直到找到一个位置，使得其代表的回文串的长度恰好为$\lfloor\frac{|S|}{2}\rfloor$ ，但是，谁知道出题人竟然用的同样是回文树，而且还考虑到了这种情况——全部都是一样的字符就可以将这种做法给卡掉了。于是，我换了种做法，每个结点我们都用一棵线段树记录，从当前结点开始，沿着后缀链走，长度为i的回文串的回文值是多少，那么，当前回文串的回文值就是线段树中，$\lfloor\frac{|S|}{2}\rfloor$这个位置的权值+1。因为要打十万棵线段树，很明显会MLE+TLE，所以我打了主席树，很快就能求出答案了。
2023年1月19日 17:03
Working together with a teammate on this question taught me an important lesson: always pay attention to the small details. I was initially confused by the lack of Chinese question faces foods that cause gout and my poor English skills, which prevented me from noticing the word "alternate" and led me to miss the correct answer. Although I was disappointed at not receiving an AK, I will take this experience as a reminder to pay close attention to all the details in the future.
2024年1月20日 14:51
JNANABHUMI AP provides all latest educational updates and many more. The main concept or our aim behind this website has been the will to provide resources full information on each topic which can be accessed through Internet. To ensure that every readers get’s what important and worthy about the topic they search and link to hear from us. jnanabhumiap.in Jnanabhumi AP is a startup by passionate webmasters and bloggers who have passion to provide engaging content which is accurate, interesting and worthy to read. We are mope like a web community where you can find different information’s, resources, topics on day to day incidents or news. We provide you the finest of web content on each and every topics possible with help of editorial and content team.