CodeChef LTIME23

VictorWonder posted @ 2015年4月27日 07:50 in CodeChef with tags 回文树 数论 数论函数变换 解题报告 , 1216 阅读

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，所以我打了主席树，很快就能求出答案了。 (输入验证码)
or Ctrl+Enter
{"ft_lang_label":"__label__zh","ft_lang_prob":0.9389926,"math_prob":0.9993222,"size":2159,"snap":"2019-26-2019-30","text_gpt3_token_len":1886,"char_repetition_ratio":0.09837587,"word_repetition_ratio":0.0,"special_character_ratio":0.23251505,"punctuation_ratio":0.02020202,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9802491,"pos_list":[0,1,2],"im_url_duplicate_count":[null,7,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-06-16T21:02:43Z\",\"WARC-Record-ID\":\"<urn:uuid:0e76feb4-da7f-4908-8ecf-1d324a6b80e2>\",\"Content-Length\":\"26489\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:6193fe6d-b005-4a0d-b15a-b2ba1eae6b63>\",\"WARC-Concurrent-To\":\"<urn:uuid:c67e9855-6af8-4873-95f2-24e37d3469e1>\",\"WARC-IP-Address\":\"198.58.112.156\",\"WARC-Target-URI\":\"http://victorwonder.is-programmer.com/posts/90002.html\",\"WARC-Payload-Digest\":\"sha1:MLLDDAWEHHVFMQ3RGID3TBCFRBMISMVX\",\"WARC-Block-Digest\":\"sha1:IHL54SZIW425K5HQG2UV2BVYOENI3QRF\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-26/CC-MAIN-2019-26_segments_1560627998298.91_warc_CC-MAIN-20190616202813-20190616224813-00056.warc.gz\"}"}