被 Matrix67 抢了先机，本来我还想来篇“最新题解”呢。

看起来是 first solver ……感觉不错。把题目给 fanhq 看了下，和我一样的做法。

Problem

只允许使用加、减、模运算，10 次操作内求出 \[f(x) = 1 + x + x^2 + x^4 \mod{2233393}\]

没坑才敢发上来的。

cgy4ever 是我最喜欢的出题者之一。他出的题代码短，思考难度高，而且非常好玩。

Solution

A

首先模拟一次，求出最后的 \(\Delta x, \Delta y\) ，然后依次枚举路径上经过的每个点，判断是否经过一定的平移后和终点重合。判断是否能重合要特别小心，不能直接算除法：如果 \(\Delta x = 0\) ，那么这个点必须和终点的 \(x\) 坐标一定相同，否则应该通过模来判。

变量忘记初始化导致连续两次 WA pretest2 好囧。不过最囧的是 FST 了……

B

分两种情况讨论。

1. 最后 \(n\) 张卡都被打完了。这种情况下肯定是先用恰好比他属性点高的最小的卡去打，然后剩下的卡一张一张打过去。
2. 最后 \(n\) 张卡没有被打完。很明显，打 DEF 的怪是不科学的，于是用我方从高到低的卡依次打对方从低到高的 ATK 卡，直到打不动为止。

C

考虑字母 A 的放置。显然 A 应该出现，而且出现最多一次。如果出现两次的话，这两个点之间的路径中就没有比 A 更高的了。不妨设标号为 A 的节点为点 \(x\) 。

考虑把 \(x\) 删掉，原树会分裂成若干棵树，任意跨过点 \(x\) 的路径都是合法的，因为不会再出现 A 了，且 A 是最高的，所以只需要依次递归处理就好了。

于是 \(x\) 该怎么选择呢？一种较优的方法是点分治，每次选择树的质心，递归层数不会超过 \(\lceil \log_2 n \rceil < 26\) 。

D

令 \(f_{i, j}\) 表示 \((i, j)\) 最后有没有被翻过来，可以证明，只要满足以下两个条件，那么 \(f\) 就是可能的：

1. \(\forall 1 \leq i \leq x, f_{i, j} + f_{i, x} + f_{i, j+x} = 0\)
2. \(\forall 1 \leq j \leq x, f_{i, j} + f_{x, j} + f_{i+x, j} = 0\)

于是我们枚举 \(f_{1, x}, f_{2, x}, \dots, f_{x, x}\) ，接下来每个 \(f_{x, i}\) 的最优解是无关的，求出每个 \(f_{x, i}\) 的最优解就好了。

E

令 \(f_{i, j}\) 表示把 \([1, j]\) 这一段分成 \(i\) 份的最小总代价。

于是我们要优化这么一种 dp ： \[f_i = \min(g_j + w_{i + 1, j})\]

容易知道， \(i\) 的决策是递增的，于是我们有一种很牛逼的方法来利用决策单调性，伪代码如下：

def work(L, R, dl, dr) :
    m = (L + R) / 2
    for i = dl to dr :
        update g[m] using i
    if L == R : return
    let dm be the optimal decision of m
    work(L, m - 1, dl, dm)
    work(m + 1, R, dm, dr)

递归层数是 \(O(\log n)\) 的，每层的总运算量是 \(O(n)\) ，总复杂度为 \(O(nk \log n)\) 。

离高考也已有三星期，忘却的救主快要降临了罢，我正有写一点东西的必要了。

preface

本性你文艺了我可文艺不起来，继续我的口水流 →_→

老改你就别吐槽这“散文”的散了……

有没有那么一种永远
永远不改变
拥抱过的美丽
都再也不破碎

前奏

我初中成绩应该是蛮不错的（gyz、lyd、wzy 等等请选择性无视），还是考得上长郡的理科实验班的。记得当时是老爸联系了向总，然后向总给我报了名，然后我就来考试了。第一次是在麓山考，结果刚发了草稿纸教育局的就来了，没能考成。第二次是在培粹考，当时是老改陪我来的。上午考完的时候由于不知道自己水平到底怎样，心里很没底。下午报复试名单时等了很久一直没等到我的名字，结果我是最后一个，吓死我了。

下午考得怎么样已经没感觉了，当时的想法是起码进了复试回去也就不会被嘲笑了。上午给我的感觉是我是最后一名，按道理下午再怎么发挥也没法进入面试。但是念面试名单时我是第一个，我都感到十分意外。后来面试的时候偷偷瞄了眼成绩单，才发现上午的名单是倒着念的……面试基本上是走过场，还是进了长郡。

后来又去了一次长沙市一中，考完感觉还可以，然后某老师把我拉过去，进行 3v1 建议。他问我有没有上过数学辅导班，看过啥数学竞赛书，居然还问了看了啥写的……总之老师似乎很希望我去的样子。后来老师透露我在那次考试是第一，自己都被吓到了。

考完市一中后，他们的成绩出得很慢，于是我就被向总拉过来试了试 OI 。等长沙市一中的成绩出了后我在犹豫是去哪里，最后还是留在长郡搞 OI 吧。

在长郡玩的时候，大概是长沙市教育局又出了个啥政策，说是允许四个学校各招十个外地生，于是长郡就把招进来的人拉过去考试，走一遍过场。于是借书去。这里得感谢杨馨茹的帮助，她向胡天中（目测你记不得我了吧）借了几本书给我。我本来就不喜欢复习，于是书放在那里，无聊了翻几翻，基本上没看过。然后就考试去了……这是我考得最好的一次了，第一。后面就再也没有过了。

然后长郡搞了个夏令营，把理实的人拉出去提前培训一段时间。然后又有个蛋疼的分班考试，我被分到了一班，挺不错的。学号这种东西应该要被遗忘在历史的尘埃里，但是前几天居然被小朋友翻出来了……这种东西不靠谱啊。巧合的是，这学号只有 0 和 1 组成，看成二进制后转成十进制，就是我高二学号后两位了。（如果我没记错的话，这也是“某人”高一学号后两位吧。）

还记得我的第一个同桌是小说哥，分寝室时认识的第一个人是彭日希。（说起来，和彭日希最大的交集就是这个了吧？但莫名其妙关系还不错的样子。）当时刘曦廷在玩魔方，我还依稀记得一点公式于是还教了他一个（虽然我自己本身就不太熟，xlk 你就不要来鄙视我啦）。

每天早上要跑操，由于我没拿啥东西来，所以解散后可以直接跑向食堂（“又一村”，永恒的回忆——一口老血喷涌而出），大部队都在后面就不必等了。大概发现了我的“优势”后就有很多人拜托我提前抢饭，最多的一次要打六碗粉。但是有一次不小心弄丢了一张票导致少打了一碗（我记得是某某人的），然后他不得不重新排队，我感到很抱歉他还来安慰我 >__<

当时不知怎么的精神很不好，上课经常睡觉，特别是物理课。思道上课简直是在催眠受不了，第一节物理课基本上是昏睡了过去的。后来思道试探性问我对物理的想法，我初中数理化中最差的就是物理了，所以谢绝了思道的好意。然后岳飞也问我是否对生物有兴趣，还是谢绝了，起码我印象中生物竞赛要背很多东西的样子，我最讨厌背这种枯燥的东西了。数学——不管怎样，我还是喜欢数学的。

于是——我的高中就这样正式开始了。

现在回忆起来的高中生活，都不完整了。

高一记起来的比较好玩的一点就是……我们班上的 yi 真是多，“逸诣翊羿屹”居然都出现了，加上三班的话“易毅” 居然还没有重复的，真是不错呢。

想起攀哥有几句经典的话啊。招生的时候说了句“我是很无私的啊”，于是获得荣誉称号——无私哥。班上一著名对联：上联“王思道”，下联“赵攀峰”，真是不错！思道说话一如既往的催眠，同学们都非常喜欢模仿他说话。万明说话很直——“这都不知道，信息组的吧”“一看你就是信息组的，这都做不出来” T_T

说到老师就不得不提到海鱼。我和高一小朋友的一段对话：“我们地理老师上课很有味的”“你们的老师绝对没我们老师有味。”“那不一定啊，你们老师是谁？”“海鱼。你们呢？”“我们也是……” 我有一段时间就把海鱼的经典语句记下来了，然后在晚自习前就在某人那里蹭啊蹭，大概有事没事就策策某人和某某人，以及说说海鱼的经典话语……某人无数次忍不住笑请我离开，她还要写作业呢。

学习分组的话，前几天和“某人”回忆了半天终于把组内有那些人记起来了：某人、某某人、我、小蛮腰、伍子逸、狗晟。同桌关系的回忆那就更加混乱了，我只记得我和某某人做过同桌，以及某人和某某人做过同桌。我又是小组长哈哈哈，从小到大一直都是小组长，然后为组名纠结了好久。我主张“自卑”，某人主张“我为学狂”，某某人的主张我忘了 = =， 然后三人靠猜拳来决定组名……后来才知道，某人主张“我为学狂”是因为这就是她初中的组名。后来我和某人一起竞选了学习委员，还有一个是王钊君吧。和某人一起工作的时候真是挺开心的。

寝室的几个人都还不错，树根、小说哥、我、骏哥、罗羿、本性几个人住一个寝室。记得住寝室的第一晚，我们集体打地铺，我就睡在骏哥旁边，骏哥玩手机开了音乐。第二天他们感慨说骏哥玩手机玩的好晚他们都没睡好，我表示离骏哥最近毫无压力。骏哥高一的时候是在看周国平的书，《灵魂只能独行》《爱与孤独》，还有一本啥，我当时毫无内涵不知道这书里面写了些啥，就开始策 →_→ too young too simple 。后来看了才知道这是哲学书籍啊。（后来赵福也在找骏哥借书看，于是我看到赵福居然在看这种书，真是一口血。）第一次听许嵩的歌是在寝室里听的，骏哥、罗羿、小说哥都挺喜欢许嵩的歌的。罗羿特别努力，我记得那一段时间都是凌晨四点就起床，我这种能晚起一分钟就不会早起一分钟的人……不说了。

我们寝室可是著名的文明寝室哦～高一的时候美术老师说了一个叫做“杀人游戏”的游戏，然后我们觉得很好玩，于是那一段时间都是在寝室玩。星期天凌晨 1 点钟开始，等老师查完寝睡觉了，我们就开始行动了，集合地点就是我们寝室。上面十二个人下面两三个人，可以凑出十多个人来。就这样一直玩了很久，直到某一次唐宇帅做了啥，导致肖老师在凌晨突然查寝，然后小人球不幸牺牲，我们寝被给了一个警告，然后就再也没有然后了……

高一的时候还处于半学霸状态，主要是学科成绩好导致做啥都没问题。例如我申请每天晚自习去机房，老师也同意了，但是还是得做作业。我做作业的速度还是比较快的，三节晚自习一般来说可以省下一节。周金鱼（→_→）天天在玩三国杀，高二学长有时候会玩游戏，但是他们的电脑刚好对着窗户，向总飘过的时候……

高一的时候有次春游，这是我唯一的一次出游啊……当时是和罗羿、本性一起啊，另外几个人忘了。这次是去长沙生态动物园，具体看了些啥忘了，但是我还记得当初在去动物园的车上赵福深情演绎《哥只是个传说》，骏哥录了音于是找他要了一份哈哈哈。说起录音的事，想起了某某人。某节晚自习下课，某某人接到一个莫名其妙的电话：“喂，是 xx 吗？我是 1016 班的一个女生嘞。我，我蛮喜欢你的……”居然还录了音，于是我又蒯了一份收藏了起来……

NOIP 2010 后莫名其妙拿了个省一。考完 NOIP 的第二天裸考模块考试，居然还能年级十几，我感到太不可思议了。（起码当时功底还不错嘛。）于是感觉没啥后顾之忧了，后面的大部分精力都放在竞赛上了。说起来发现我逃了一堆的考试啊，似乎巧妙地避开了所有期末考试，期中考试也避开了大部分，导致后来填档案的时候一查发现没有可以用的期末考试的分数，唯一一次要记在档案里的是水考成绩——我就不说这是我有史以来考得最差的一次了。

高一上期数学组报了个 AMC 比赛，结果有人临阵来不了，于是求一个炮灰。然后我就成为了光荣的信息组大炮灰，结果莫名其妙进了复赛了。其实这啥 AMC 我都不知道是考啥的，一堆人没进复赛目测都是没看懂题啊。不管了，三个进复赛的，一个是现役数学组，一个是退役数学组，还有一个是信息组炮灰，真好 = =。但是最囧的就是，AMC 的复赛和我第二次春游冲了，于是惨淡的不能参加春游好惨 T_T 这次某某人邀请我参加他们组啊……

某人和某某人的事，不知道是啥时候开始就有人策了，但我一直在且仅在某人面前策。某某人于 2011.4.4 正式退出物理组（不要问我为啥记得这么清楚），下午和我一起吃了顿饭，说自己坐不住什么的。我还是为他感到很可惜呢。后来某人和某某人联系就不多了，据说是因为家长吧。想起骏哥和黄子寒的事，这在当初也是沸沸扬扬的，后来老李谈了次话吧，然后就没有然后了，不知道他们现在关系怎么样。某人和赵福感觉最好玩了，一个沉稳，一个张扬，某人经常“举起她那坩埚大的拳头”，然后赵福就开嘲讽 mode ，经常是以某人的失败告终……

某篇日记里写了三个人，简称分别是 sb，ssb，P ，我来解释一下吧：sb -> somebody，初中记笔记经常用的；ssb 同理；P = mv -> MV -> 兆伏，某人当年在好题分享中写了个 mv 感觉还是没几人看得懂的。本性大概是策我策的最多的吧，谁叫我们同寝那么久，661314277 还记得这个数字吗……（错了的话就不要在意这些细节了）说起来你的枕头怎么处理，高一的时候给我了，现在还在我这里。

说起我和赵福，倒还是由两个故事的。第一个故事是，他母亲的同事是我爸的学生……我不知道他是怎么知道的，但是莫名其妙就出现了。另外一个故事是关于手机的。众所周知，赵福是没手机的，因为他自控力差，经常玩手机。于是他经常借树根的手机玩，树根也不想借给他，但是每次都被他“抢”了过去。于是后来树根就说，他爸妈有时候会打电话过来，看他睡觉没有，说要他睡觉的时候关手机。赵福问啥时候打过来，树根说不知道。于是，某天晚上，我和另一人（根据相关法律法规）就一直打树根电话，因为树根手机里面没有存我们俩的手机，开始几个电话赵福按掉了，后来根本就不按了，再后来就关机了。我们总过打了差不多二十个电话吧。第二天树根问赵福有没有电话打过来，赵福回答“在十一点半的时候电话打个不停都烦死了”，树根马上接一句“那肯定是我父母了”。后来某一天中午，树根父母来了，于是把树根拉出去吃顿饭。赵福又来借手机发现树根不在，于是罗羿说——“树根被他父母叫出去了。” 说完后停了停，继续说：“似乎树根有点不开心。”赵福问为啥，罗羿说“他父母给他打电话发现他没关机”……好一个临场发挥！说完后他装作很困的样子睡觉去了。等赵福走后，他抬起头来满脸都是笑容，说：“我快憋不住了……”

我记得寝室里谁有一次生日吧，我们全寝等到十二点，一起唱生日歌祝福生日快乐，唱着唱着我好感动 >__<

自从做了语基题，我再也不敢乱读字了。“参与”的“与”居然不是第三声，是第四声！这东西看起来就怕啊。

本性喜欢看科幻小说，他那里积累了一垛的《科幻世界》，于是我有时候也借他的《科幻世界》看。本性很推荐三体，于是某一天中午我就拿起一本《三体·黑暗森林》看。我看书的习惯是随手一翻，翻到哪里就看哪里。当时是翻到罗辑给大史讲解他的黑暗森林理论。看着看着发现这本书的某一个后缀就被我看完了，感觉不过瘾，从头看《黑暗森林》，虽然不知道《地球往事》的一些情节，但是仍然看得津津有味。某一次出去比赛的时候，本性顺便把《地球往事》也带了出去，于是我又把《地球往事》看了，最后决定看《死神永生》，感觉这是一个冷酷的宇宙，“没有人性，失去很多，没有兽性，失去一切”。（虽然我很喜欢三体并推荐了别人去看，但是不是每个人都有兴趣的……）（说起来最近看了《嫌疑人 X 的献身》也挺有感触的。）

自从进了高二，我就把学科抛弃了。高二又是 NOIP 停课、WC 停课的节奏，就考了一次期中考试。这次期中考试虽然考的不是很好，但是从名次上来看是不错的。信息组成绩喜人，全部进了班上前十——因为只有信息组考了。一班其余竞赛组没参加，二班三班参加高三的模拟考试去了。一开始和平行班同学聊天的时候他们说啥一班有个很厉害的人也要来考试，我就只能笑笑不说话了——都成学渣了好吗……但是那次考试由于一群学霸没来，导致还能进年级前十，真是不可思议。平行班的尖子生都被拉进二班三班了好吗，要是一二三班的学霸过来的话目测要年级 100+ 了。（@wzy 所以说也是 f_i = f_{i - 1} * f_{i - 2}）

高二下期刚开学就停课了，但是中间有个水考不得不准备一下。果然模拟题和真题是两码事。我记得一开始的水考模拟题，政治 61 分勉强保住不挂科，物理 56 分真就挂科了。我向来是不惮以毁坏的恶意，来推测我的学科的，然而我还不料，也不信竟会颓废到这地步。况且始终微笑的和蔼的物理君，更何至于特意在水考前挂科呢？我还有什么话可说呢？我懂得挂科学生之所以默无声息的缘由了。竞赛呵，竞赛呵！不在竞赛中保送，就在学科中煎熬。信息组物理最高分 58 分，也就是全体挂科的节奏。我就不说我连题目都看不懂了。从各科平均分来看，只有物理组的数学平均分比我们低，其余的各科信息组都是垫底，不能多说了。后来政治发哥给我们划了若干重点后，背了几天感觉不错。历史地理之类的看看就好（忽然换老师了，想念海鱼啊）

后来水考的时候……哈哈哈这也是考试？……哈哈哈这题目有谁过不了？除了语文和英语没有提前交卷外，其余我都是半个小时就撤。化学由于在答题之前老师就把卷子发了下来，于是我就在开考铃响之前把卷子做完了。很难想象我居然每科都达标了，语英政史地都不低于 90 分，数理化生都有 95 （没打满分真心不爽）。虽然是这么说，可是这却是我年级排名最低的一次——我就不说年级 600+ 了……满分 900 我们学校最高分 896 （@小蛮腰），真是可怕。后来填成绩的时候期末考试找不到我的名字，但是水考还是有我的名字的，于是学校记录的我的年级最高排名就是 600+ 了哈哈哈。不过话说我们这届考得蛮好的，按照 90% 左右的一本率，参加高考的话还是有可能的上一本吧——问题是能不能保持年级 600+ 啊。

水考之后再无学科。回顾我的学科，往事还堪回首，现实不忍直视！（@某人，@wzy）在高三第一次月考之后，和某人一起走过排名榜前，听见有人说：“周子青这次没考好啊，她还会不会再来虐一次？”当时我就差点笑喷了。记得某人在准备保考的时候，那真的就是被虐的飞起，数学 5 分物理 4 分。看到当年的学霸也沦落到这地步，顿感世事苍凉啊，我们真就是壮士了。（感觉 @正兴 大概是唯一一个没有退化的学霸了吧，求拯救 >__<）

在班上担任的职务嘛，高一高二的时候还搞了个电教委员，但是后来根本就没时间管理了真是对不起 >__< 以及我和某人两个人管理的学习委员（捂脸），在高一的时候还好吧，高二的时候已经无暇顾及了，于是把很多工作全部抛给了某人。在担任学习委员的时候私自藏了若干东西（一垛一垛的草稿纸），于是现在草稿纸多的用不完。

本性退出信息组后，开始了漫长的学科生涯。其他竞赛组都停课了，班上就只有他一个人了，于是都是 1v1 专业辅导。后来生物组加了进来，于是就不再是 1v1 了，但是生物课上仍然是 1v1 。生物组的那堆学霸，真的不忍直视。高考全校前四，有三个曾经在生物组学习过 = =

高二暑假倒是过得蛮爽的。考完 NOI 后四处旅游，先去了杭州，在西湖玩了玩，然后去了九溪玩玩。回长沙后呆了几天我和我老爸一起去汕头、潮州那边去玩，后来又去了惠州，住了一个晚上啥都没做就会老家了。老家和同学见了几面，然后就去贵阳玩。贵阳温度真心低，度暑假什么的最舒服了。过一段时间也要到贵阳那边去玩玩，然后就去帝都了。

说起体育运动，这也是我的伤心痛苦的往事。本来我这瘦小的身材也不适合做激烈运动，跑跑步之类的还算可以（毕竟体重轻），小球也还打的下，但是大球一个都不会。高一的时候是乒乓球班的，于是学了一点基本的乒乓球打法。前几天和某人及其父母打球的时候我都是削球，老师教的基本上没派上用场。当然我也只会削，抽的准确率真的高达 10% 不到。至于水平嘛，那真心不咋地了。冬天的时候我们打了很久的乒乓球，因为有乒乓球室而没有羽毛球室，要打羽毛球的话得在足球场上旁边的两个小场地里面打，冬天风那么一吹，不能更爽。打乒乓球的话树根一般也会来凑凑热闹，通常来说秋锅独领风骚，一人霸着台就不下了。很少可以把秋锅打下去，我和树根轮着打，有时候小小的爆发一次还是可以把他打下去的。不过满屋子捡球真的很累啊，那种乱抽的人你是怎么想的靠这样消耗别人体力么。小朋友也和我们一起打乒乓球（NOIP 的时候），我们一般会霸 2 - 3 个桌子，打起来很带感的。

另外一个打得比较多的是羽毛球。从运动量来说，羽毛球比乒乓球的运动量是要大些。由于我停课停了很久，停课的时候我们每天下午五点后就去打羽毛球。一开始是我、tw、本性、天聪几个人来双打，小字母贡献了一副羽毛球拍以及家长委员会也有一副，另外信息组自备若干劣质牌子，所以说拍子是足够的，但是球就不一定了。球基本上是一天一个的节奏，快的话一天两个都有可能。乒乓球的器材很普遍，因为乒乓球室里面都是球，打了球之后球的个数甚至会增加，但是羽毛球就是打一个少一个了 = = 好囧。于是谢老师发挥了她的社交才能，从器材室给我们拿来了一些球，质量感觉不错。后来本性走了，我、tw、天聪几个人在打球。后来 tw 也走了，于是我、整容、天聪几个人打球。后来天聪也走了……幸亏新高一的来了，于是我就和新高一的一起打球。why 经常把我虐残了。我在我们班上球技也顶多算个中等，虽然在信息组内排名是比较靠前的。晓涛大概对我的“普通攻击”无语了吧。天聪和我都是比较喜欢打反手的，于是经常我们打着打着就是反手系了。另外一点是天聪一旦在网前得到一个高球，那么基本上可以判定对方死局了。当然防御力高的话还是可以接到的，我还是可以接到几次的 = = 春宵打球就是个奇葩（其实他做啥都有点奇葩，信息组公认），经常做一个炫酷叼炸天的动作，然后就没有然后了。说起来，大叔是被我坑的最惨的人了吧，我和他打球基本上不超过 10 个球，他就会被我坑。但是有一次天聪和他组队，于是我就不敢坑了，天聪网前防御力太高，甚至直接将防御转为攻击。其实后半场左右吊球也是不错的，大叔继续被我坑。

打羽毛球打的最爽的一次是那次基哥请我们在贺龙旁边的一个体育馆打球。当时不知怎么的体力特别好，打了一上午就停下来喝了 30s 的水，其余时间一直在和别人打。基哥也是坑人好手，大叔打球大概是杀伤力比较大（一贯作风），但是防御力很低。这让我想起主丰。主丰的攻击力真心强，那么高的人（xlk 请无视）给你扣一下，被打倒了真的不是好玩的，杨 RR 都被打到过。但是主丰的防御力不敢恭维 = = 大概也是身高的缘故吧。班上一堆人一起打球还是很开心的。有时候二班的也会过来凑凑热闹，例如某某人之类的 = =

高三的生活是比较舒服的，记得暑假的后几天，我都不知道该怎么过了，于是就参加网上的一些比赛，顺手还收了件 T-shirt 。

高三发现也没啥好讲的。我大概就是窝在机房里不出来了。招生办的话……说起来有一次谢老师要我们去招生办做一天工，然后点名点了几个同学要他们去。于是我们几个干了一天的活。后来谢老师特意问我哪些人去了，然后我就说了 balabala 一堆人的名字，谢老师就公开表扬了这些人。秋锅在一旁表示很无语，他以前经常被拉去招生办做事，结果谢老师一直没问，我们就做了这一天就得到了谢老师的表扬，感觉很囧。高三还有个支教活动吧，没去的也就信息组 + 正兴 + 某人 了。其实现在想想支教应该还是蛮好玩的，虽然据说那里没热水不能洗澡厕所味道不敢恭维虫子满天需要特别防护。

由于保送生也有这么多吧，学校也就开了个保送生班，放在三教一楼，这也是上届保送生班的位置。去年这里是集体堕落的地方。今年情况就好很多了，李姐要求我们在这里早自习，一开始还有些人来，后来根本就没人了。集体堕落处改为一教四楼或者科学馆三楼了，而且保送生教室经常被占，导致我们都不想去那里了。直到后来骆总亲自上阵，取缔了科学馆三楼，人民群众喜大普奔，保送生们表示只能混招生办了。

说起来想起了在 cjoier 群里面发生的一件事，平行班的保送生们大概都知道吧。大概就是我代 miffy 宣传支教活动，于是很多保送生就在询问这事。但是 miffy 没加这群，于是只能有我代他们询问，大概我就是个中间人吧。然后某一次，miffy 洗澡去了，没能及时回那些问题……于是周鲸鱼（→_→）就说：“快问问你的 miffy ……” 我：“不，是你的 miffy ” 后来周鲸鱼就说：“你的 miffy 不理你了么……” 然后我就跟着开玩笑说：“都是你的错，我的 miffy 都不理我了……”于是大家集体声讨周鲸鱼，我继续卖萌，钓出了好多潜水党。后来再看真是不忍直视，现在“我的 miffy ”都是一个梗。

WC 跪了之后就开始玩自己的事了。结果现在发现啥都没玩出来呢。和别人一起出了两场 CF ，（结果主席出着出着心脏就跪了），苦力费表示还没拿到。衣服倒是混了几件。四月下旬的时候参加了腾讯的 onsite 。本来就是打酱油的结果坑了队友 →_→ 。幸亏我们组中我和 wzm 都是过来旅游的。第一天晚上有场 CF ，但是看了题目就不想做了。于是和别人聊天聊到两点。突然发现我还失眠了，早上六点钟就起来了，几乎没睡。然后这一天又是开始写工程了。发现我们工程速度好慢，于是开始搞通宵。微软编程之美的复赛恰好是在这天下午，我没一点精力，于是就拜托 xlk 帮我做。莫名其妙就进了 onsite ，结果 MS 说不是大学生不可以真是 ** 。中午实在是困了就躺着眯了一小下。接到翔打来的电话通知省选情况，实在是没力气了，就有气无力的回了几句。那时候我发现由于长期做比赛，导致视力严重退化，又熬了这么久的夜，看东西都是眯起来的，视力应该只有 4.4 左右了。于是从那以后就没再怎么熬过夜了，除了 GCJ 之类的。现在应该回到了 4.8 了吧。（可还是太低了啊）

五月份 PKU 搞了个校赛，于是 xlk 把我和 qdc 拉过去组了一队。最后 #8 还拿了个包。大概就是一等奖 4 个，每人 6k ，二等奖若干个，每人一个书包，三等奖若干若干个，一个“精品马克杯”。我就不吐槽这奖品的差距有多大了。说起来来帝都的第一天，我要到腾讯某地方去报销车票，结果拉着 xlk 从人大一路走到了清华。后来又到清华逛了一圈。你能想象坐地铁过来然后走回去的场景吗……后来我们三个找宾馆，找到了锦江之星双清路店，发现旁边啥东西都没有，周围环境太糟糕，于是就换地方了。我们准备从双清路店走到最近的一个地铁站，结果走到了一个奇怪的立交桥，在立交桥那里都要转晕了，幸亏最后队友给力。换到了锦江之星奥体中心店，还算可以吧，平均下来一天 100 也不是很贵。我们到 THU 的时候去找了某盾。某盾熬夜熬到早上，我们来的时候他还在睡觉。果断把他喊起来。然后我们就到楼上去找 ayq 和 zpl 。zpl 回家去了，于是我们就问 ayq 关于 THU 的一些事。据说大物很恐怖，有种要跪的感觉……中午我们三个蹭了某盾、LR0 和 ayq 一顿饭，去吃那个啥青青披萨（其实我还没吃过 pizza 呢），开学后再请他们一次好了。下午就去隔壁蹭基哥，lich 和 dyf 都有事，qdc 某学姐忙着搞活动。PKU 的未名湖看起来比 THU 的臭水沟好多了……然后我就不得不吐槽 MS 了。MS 复赛我明明要别人帮我做了的啊，你居然说我什么还不是大学生没法参加 onsite ……这不坑爹么。刚好 MS 的复赛就在我走的那天，这表示如果 MS 让我参加 onsite 的话，我就可以省下来回的车票了……1k 啊……MS 给我唯一的补偿是一个包，衣服什么的都不给我来一件 = =

六月份就是高考了。由于本性在明德，我就自告奋勇去了明德送考。同行的还有正兴和 miffy 。第一天我们去的时候 miffy 就没来了，abin 被调过来了。幸亏事也不是很多。大概就是保证每个人能够准确无误的进入考场吧，然后给些精神鼓励之类的。“我站在走廊的这一端，看着他逐渐消失在教室的门口，而且，他用背影告诉我，不必追”，大概就是这种感觉吧。

两天中午都跟着老师蹭饭。第一天上午比较无聊，因为我就拿了一本文艺书籍过去，结果看不下了。于是正兴开始给我做题，我这水平还能做出啥题 = = 不过居然做出了一道小题没爆零（1.5 pts）真是太开心了。后来我们就在聊关于推理电影的事。某个老师被他们班的学生要求写毕业寄语，于是她就把任务交给我们，这不坑爹么。我第一想法是《面朝大海，春暖花开》的倒数若干句，结果刚说出来就被喷成“没文化”，真是一口老血喷出来，这可是我少数能够记得的用来装逼的几首诗啊 →_→ 果然装逼遭雷劈么。第二天我就把笔记本电脑拿了过去，和正兴一起看《言叶之庭》。正兴看了不断评论“真是太文艺了”。我还想给他看看秒五，结果发现字幕没搞好就看不了了。下午屹大王来了，于是玩起了 MC 。由于大家都不会玩，一开始是一顿乱玩，例如建造一个游泳池之类的，后来我们就开始建造我们的终极工程：高台跳水。首先是 abin 建造他的跳水台。让我们期待一下 abin 的第一次跳水——成功跳到了地上！后来几次都是跳到了冰上。后来屹大王也开始建造他的跳水台，高度比 abin 的还要高。然后让我们拭目以待——屹大王成功跳到了一块石头上！经过调查研究发现，这块石头是这附近唯一一块石头！其余的石头全被我们清理干净了，就这一块没有被清理……屹大王的 RP 真是太好了。

毕业典礼。看了那个煽情的视频后，眼泪不停地打转。想起我当年来长郡的时候，还是个小孩。现在要离去了，却也是舍不得。我曾以为我对东方红没什么感情，但是离开的时候不住的回头。现在我们要走了，我会怀念这里的。整容给我送了一张明信片，看着他的字迹，想着以后就有可能很难再见了……真是很伤感呢。李姐和我们每个人都拥抱了一下，那将永远是值得信赖的依靠（虽然也被卖过……）。

七月初，班上最后一次聚会。这大概也算得上是高三以来聚得最齐的一次了。某人正兴都来了，这很不容易啊。和诺诺一起卖个萌，和屹大王玩玩三国杀，偷拍一下本性。酒……那还是算了吧（本性你能喝啊，专业代我喝酒吧）。最高潮的地方就是岳飞一个一个介绍生物组的孩子。然后我就光荣的被小字母卖了。大概是声音很大引来了谢老师，于是谢老师还提议喝交杯酒 →_→ 最后我和某人就用饮料代酒碰了一杯。高中的回忆，美丽的青春。

至此，高中生活，终结束。

epilogue

人有悲欢离合，月有阴晴圆缺。

过去的生活，就让它以记忆的形态变成过去的历史吧。

真的猛士，将更奋然而前行。

呜呼，我说不出话，但以此记念高中君！

（居然写了 1w+ 字，真是不容易啊）

有没有那么一张书签
停止那一天
最单纯的笑脸和
最美那一年

nonsense

最近好忙被老师托着做了一堆事 = =

一直没更新了，居然被 M67 抢了上个月的 UyHiP ……我还是 first solver 呢 →_→

最近刷水好严重的。

（其实主要是各种被抓苦力。）

Problem

是否存在一个 \(n \times n\) 矩阵 \(f\) ，使得每一行的和均为 1，且存在一组 \(p_{1, \dots, n}\) 满足 \(p_1 = 1, |p_i - p_{i - 1}| \leq 1\) 且 \[\sum_{i = 1}^n f_{i, p_i} > H_n = \sum_{i = 1}^n \frac{1}{n}\]

最近做的两道题。

感觉很囧啊，数学全忘了啊。

Google-Codejam-Round3-D

果然 GCJ 滚粗是必然的。

考虑一个事实：在 \(i\) 到 \(j\) 这一段的一个位置 \(k\) ，如果 \(k\) 是 . ，那么 \(i\) 到 \(k\) 和 \(k+1\) 到 \(j\) 是独立的，即，如果某次一个人进入摩天轮时，他遇到的第一个格子在 \(i\) 到 \(k\) 之间，那么他最后占领的格子一定会在 \(i\) 到 \(k\) 中而不会在 \(k+1\) 到 \(j\) 中。

于是就倒着来思考。首先明显的在最后只剩下一个空的时候，期望是固定的，为 \(\frac{n - 1}{2}\) 。

所以我们枚举最后一个空的位置，然后转为序列上的问题。

序列上的问题有明显的子结构：令 \(f_{i, j}\) 表示原序列的 \(i\) 到 \(j\) 这一段，经过若干次操作后，除位置 \(j\) 为 . 以外，其余的元素均为 X 的期望代价， \(p_{i, j}\) 表示概率。令 \(P(i, j, k)\) 表示 \(i\) 到 \(j\) 这一段， \(j\) 一直是 . 的，最后一个转为 X 的 . 的位置为 \(k\) ，其余的都是 . 的概率。

\[P(i, j, k) = \binom{Lk + kR}{Lk} (\frac{k+1-i}{j+1-i})^{Lk+1} (\frac{j-k}{j+1-i})^{kR} p_{i, k} p_{k+1,j}\]

其中 \(Lk\) 表示初始状态中 \([i, k - 1]\) 中 . 的个数， \(kR\) 表示 \([k+1, j-1]\) 中 . 的个数。由于最后一个转为 X 的 . 为 \(k\) ，所以我们要考虑到前 \(Lk + kR\) 次 X 变 . 的顺序，所以要乘以一个二项式。再乘以有 \(Lk + 1\) 个落在 \([i, k]\) 的概率，以及又 \(kR\) 个落在 \([k+1,j]\) 的概率，最后乘以合法的概率 \(p_{i, k} p_{k+1,j}\) 。

所以得到 \(f\) 和 \(p\) 的转移如下：

\[ \begin{array}{rcl} p_{i, j} & = & \sum_{k = i}^{j - 1} P(i, j, k) \\ f_{i, j} & = & \frac{1}{P_{i, j}}\sum_{k = i}^{j - 1} P(i, j, k) (f_{L, k} + f_{k+1, R} + n - \frac{k-i}{2}) \\ \end{array} \]

注意 dp 时的 \(i\) 可能大于 \(j\) ，因为这是环状，所有计算长度的公式都需要进行一定的修正。

TopcoderOpen-Round3-Level3

\(\newcommand{\stirone}[2]{\left\{ { #1 } \atop { #2} \right\} }\) \(\newcommand{\stirtwo}[2]{\left[ { #1} \atop { #2} \right] }\) jzp 的神题，我表示被吓傻了……

我还是直接上 传送门 吧……我就写写我的感觉 →_→

主要思想

感觉非常牛逼啊。

1. 用容斥写出答案的表达式
2. 观察这个表达式和 \(\Delta^n f(x)\) 很像，于是用 \((-1)^n \Delta^n f(x)\) 来求答案
3. 具体化 \(f(x)\) 。如何求 \(\Delta^n f(0)\) ？考虑写成 \[f(x) = \sum a_i x^i = \sum b_i \binom{x}{i}\]
4. 可以得到 \[\Delta^n f(0) = b_n\] 所以求 \(b_n\) 就好了……

一些细节

考虑如何求 \(b_n\) ？利用 \[x^n = \sum_{k=0}^n k!\stirone{n}{k} \binom{x}{k}\] 可以得到 \[b_n = n! \sum_{k = n} \stirone{k}{n} a_k\]

于是我们只要求 \(a\) 就好了。利用 \[\binom{n}{k} = \sum_k \stirtwo{n}{k} (-1)^{n-k} x^k\] 可以拆开一个 \(n\) 中含有未知数的二项式。

如何求两类 stirling 数？题目中说了 \(m - n \leq 10^3\) ，于是我们要在 \(m - n\) 相关的的时间内求出所有涉及到的 stirling 数。假如我们要求 \(\stirone{n}{m}\) ，当 \(n - m\) 特别小时，考虑 \(\stirone{n}{m}\) 的实际意义，表示将 \(n\) 个数分成 \(m\) 个环的方案数，至多有 \(n - m\) 个环的大小不为 1 ，这些环的大小之和至多是 \(2(n - m)\) ，于是考虑 \(f(i, j)\) 表示 \(j\) 个大小大于 2 的环的总大小为 \(i\) 的方案数，可以得到一个和 stirling 数类似的递推。

从 xiaodao 空间上看到的……

感觉蛮好玩的于是就试了试。xiaodao 最后的那个连乘真的没有想到，我只会暴力积分……

Problem

\(d\) 维单位球体中随机选 \(n\) 个点，到球心 \(k\) 远点距离球心的期望是多少？

Solution

\(n\) 个点，随机选一个为 \(k\) 远点，再选 \(k - 1\) 个点为前 \(k - 1\) 远点，方案数为 \(\binom{n}{1, k - 1}\) 。

（维基百科） \(d\) 维单位球体的体积是 \[V_d(R) = \frac{\pi^{\frac{d}{2}}R^d}{\Gamma(\frac{d}{2}+1)} = C_d R^d\] 其中 \(C_d\) 为与 \(d\) 相关的常数。

根据“维”的定义，我们有距离为 \(r\) 的点的密度为 \[\rho(r) = \frac{V'_d(r)}{V_d(1)} = d r^{d - 1}\]

于是 \(k\) 远点的期望是： \[\begin{array}{rl} & \binom{n}{1, k - 1} \int_0^1 r \rho(r) (r^d)^{k-1} (1 - r^d)^{n-k} \mathrm{d} r \\ = & d \binom{n}{1, k - 1} \int_0^1 r^{kd} (1 - r^d)^{n-k} \mathrm{d} r \\ = & nd \binom{n - 1}{k - 1} \int_0^1 r^{kd} \sum_{i=0}^{n-k} \binom{n-k}{i} (-r^d)^i \mathrm{d} r \\ = & nd \binom{n - 1}{k - 1} \sum_{i=0}^{n-k} \binom{n-k}{i} (-1)^i \int_0^1 r^{kd+id} \mathrm{d} r \\ = & nd \binom{n - 1}{k - 1} \sum_{i=0}^{n-k} \frac{\binom{n-k}{i} (-1)^i}{kd+id+1} \\ \end{array} \]

这样做的值应该是没错的，但是精度误差特别大 >__<

于是我们还需要继续化简……

我对如何操作二项式已经忘得差不多了，于是无意间拿起 CM 居然看到了这货：

对于函数 \(f(x)\) ，定义 \(\Delta^{(0)} f(x) = f(x)\) 。然后可以定义 \(\Delta^{(n)} f(x) = \Delta^{(n - 1)} f(x + 1) - \Delta^{(n - 1)} f(x)\) ，然后可以得到： \[\Delta^{(n)} f(x) = \sum_{k} \binom{n}{k} (-1)^{n-k} f(x+k)\]

注意到 \(\Delta^{(n)}f(x)\) 的表达式与要化简的那个式子中的比较像，考虑令 \(f(x) = \frac{1}{x}\) ， 用 \((-1)^{n-k} \Delta^{(n - k)} f(x)\) 来代替 \(\sum\) 。

\[\begin{array}{rl} & nd \binom{n - 1}{k - 1} \sum_{i=0}^{n-k} \frac{\binom{n-k}{i} (-1)^i}{kd+id+1} \\ = & n \binom{n - 1}{k - 1} (-1)^{n-k} \sum_{i=0}^{n-k} \frac{\binom{n-k}{i} (-1)^{n-k-i}}{k+i+\frac{1}{d}} \\ = & n \binom{n - 1}{k - 1} \Delta^{(n - k)} f(k+\frac{1}{d}) (-1)^{n-k} \\ \end{array}\]

由于 \(f(x) = \frac{1}{x}\) ，我们又有： \[\begin{array}{rcl} \Delta^{(1)} f(x) & = & \frac{-1}{x^{\bar{2}}} \\ \Delta^{(2)} f(x) & = & \frac{2}{x^{\bar{3}}} \\ \Delta^{(3)} f(x) & = & \frac{-6}{x^{\bar{4}}} \\ \end{array}\]

其中 \(x^{\bar{k}} = \prod_{i = 0}^{k - 1} (x+i)\)

可以找出规律（然后归纳法）\[\Delta^{(n)} f(x) = \frac{(-1)^n n!}{x^{\bar{n+1}}}\]

继续代入： \[\begin{array}{rl} & n \binom{n - 1}{k - 1} \Delta^{(n - k)} f(k+\frac{1}{d}) (-1)^{n-k} \\ = & n \binom{n - 1}{k - 1} \frac{(-1)^{n-k} (n-k)!}{(k+\frac{1}{d})^{\bar{n-k+1}}} (-1)^{n-k} \\ = & \frac{n!}{(k-1)! (k+\frac{1}{d})^{\bar{n-k+1}}} \\ = & \frac{n!}{(k-1)! \prod_{i=0}^{n-k} (k+i+\frac{1}{d})} \\ = & \frac{\prod_{i=0}^{n-k}(n-i)}{\prod_{i=0}^{n-k} (k+i+\frac{1}{d})} \\ = & \prod_{i=0}^{n-k} \frac{(n-i)}{k+i+\frac{1}{d}} \\ = & \prod_{i=k}^{n} \frac{i}{i+\frac{1}{d}} \\ = & \prod_{i=k}^{n} \frac{di}{di+1} \\ \end{array}\]

这样化简的结果和 xiaodao 的方法是一样的……真是太开心了 @_@ ……

Epilogue

这推导真是恶心死我了……

学的东西都忘光了怎么破……

写的公式太多了感觉会跪？ @dyh 求查错……

Markdown 里的替换

大概是为了防止 TeX 里面的 _ 和 ^ 被转义而写的。由于要改多次……还是先记下来吧。

\([^\]\)^ -> \1\^
\([^\]\)_ -> \1\_

好久没做题了，前一段时间旅游了一小会儿然后趁着 **USC 的机会溜回家开始了长达七天的暑假生活。

闲着无聊做了一下 PE-432 ……

Problem

令 \[S(n, m) = \sum_{i=1}^{m} \phi(n \times i)\] 求 \(S(510510, 10^{11})\)

Solution

令 \(n = pq\) ，且 \(p\) 为质数，有 \[ S(n, m) = (p - 1) S(q, m) + S(n, \lfloor \frac{m}{p} \rfloor)\]

于是我们只要计算 \[S(1, m) = \sum_{i = 1}^m \phi(i)\] 即可。

线性筛法可以去死了。我们可以采用 @dyh 的理性愉悦 \(O(n^{\frac{2}{3}})\) 的方法：

令 \(S_f\) 表示函数 \(f\) 的前缀和函数，即 \[S_f(n) = \sum_{i = 1}^n f(i)\] 。我们要求 \(S_{\phi} (n)\) 。

令 \(g_n = \sum_{d|n} f_n\) 于是有 \[S_g(n) = \sum_{i = 1}^n \sum_{d|i} f(d) = \sum_{i=1}^n S_f(\lfloor \frac{n}{i} \rfloor)\] 这个等式只要注意到每个 \(f(i)\) 被加的次数都是 \(\lfloor\frac{n}{i}\rfloor\) 就好了。

如果我们能够快速计算 \(S_g(n)\) ，就可以利用 \[S_f(n) = S_g(n) - \sum_{i = 2}^n S_f(\lfloor \frac{n}{i} \rfloor)\] 来计算 \(S_f(n)\) 了。

当 \(f(n) = \phi(n)\) 时， \(g(n) = \sum_{d|n} f_n = n\) ，\(S_g(n) = \frac{1}{2} n(n+1)\) 。我们用筛法算出 \(i \leq n^{\frac{2}{3}}\) 时的 \(S_f(i)\) ，其余的暴力记忆化递归做下去，复杂度是 \(O(n^{\frac{2}{3}})\) 。

我一开始把 \(m\) 看成了 \(10^{14}\) 跑了 20min 才跑出来， \(m = 10^{11}\) 时只要 3s 就可以了……

这几天都忙着高考送考（以及考后狂欢）去了。一年毕业季，一年别离时。

（祝在高考这天生日的同学年年有今日，岁岁有今朝 23333）

IPSC 2013

IPSC 的题感觉蛮好玩的，但是非常难……

我一开始还没组队，然后 dyh 拉我组了一队，然后我就把 xlk 拉了进去。事实证明把 xlk 拉进去是个非常正确的决定。

practice

P

easy：不说了 - -

hard：看了 solution 才发现坑爹啊……居然连 l33t 语都出现了……我还是不吐槽了 >__<

Q

easy： 显然很水 - -

然后我就不会 hard 了 - -

hard：显然平均数是可以被忽略的。我们要构造的是方差，也就是找到一组 \(a_{1, \dots, n}\) 使得 \(\sum a_i = 0\) 且 \(\sum a^2_i = nv\) 。

考虑如下构造：序列长度为 \(2n\) ，且 \(a_{2k - 1} = -a_{2k}\) ，那么第一个限制显然就满足了，第二个限制直接贪心就好。

R

easy 也不难，(a-z)*25+a 就可以了。

然后 YY 了好久的 hard 没想法。于是我把很小的 n 的解的长度打出来放到 OEIS 上搜，发现了 这个序列 。OEIS 上还顺便提了一下某种较优解的构造方法，然后就没有然后了。

题解也是用的这种构造……

formal contest

完全不会啊亲……

所以你是来看题解的话是找不到任何东西的哈哈哈哈。

待我先去研究一番题解……

A

其实我没看题 2333

B

看了一眼后发现……这不是某个经典结论吗亲……

这个题我曾经 YY 过一个证明方法：令一个数 \(n\) 的势能 \(\phi(n) = \frac{n^2}{2}\) 。那么将 \(n\) 分成 \(x + y = n\) 两份时，释放的能量为 \(\phi(n) - \phi(x) - \phi(y) = xy\) ，这表示将 \(n\) 分成若干个数，释放的能量与具体分法是无关的。那么将 \(n\) 分成若干个 1 ，无论怎么分，释放的能量总为 \(\phi(n) - n \phi(1) = \frac{n(n - 1)}{2}\) 。

我以前一位同学 YY 出另外一个证法：考虑图 \(K_n\) ，把 \(n\) 分成 \(x+y = n\) 对应着图上选择两个点集，大小分别为 \(x, y\) ，并将这两个点集之间的 \(xy\) 条边的删掉。那么初始的时候有 \(\frac{n(n-1)}{2}\) 条边，结束的时候没有边（ \(n\) 个孤立的点），所以一共删了 \(\frac{n(n - 1)}{2}\) 条边。

C

easy ：你把函数 t 的值打出来，可以发现 \(t(n) = \phi(n) + 1\) ， \(\phi\) 为欧拉函数。

然后就可以直接跑了。这样会输出一个指令，然后照着这个指令依次做下去就好了。

为啥我和 dyh 都跑不出指令，就 xlk 可以？

hard ：可以得到当 \(b > 500\) 时， \(g(b)\) 一定是 1 。然后每次求 \(g\) 就可以 \(O(1)\) 求，然后会输出一堆点的坐标。然后就不会了……

题解如是说：把这些点的坐标全部画出来，然后可以得到一个二维码，用手机扫描可以得到一句话：88767->7123398 ，然后就是 easy 的节奏了。

D

easy： 就是昨天 R 的 checker 。首先我们想怎样检验一个排列是否出现过？肯定是每次选择最近的一个下一个字母。所以这样就可以 dp 了。 \(f_S\) 表示集合 \(S\) 中的所有元素按照一定顺序全部出现，所有的顺序中，最后一个字母出现的位置最靠后的一个位置是什么。转移的话枚举下一个字母就好了。

我写的比较渣，跑了 10min 才跑出来 >__<

hard：如果继续按照这个思路去做的话， \(f_{S, t}\) 表示集合 \(S\) 的排列中，最后一个元素出现的位置是 \(t\) 的方案数，内存会受不了 >__< 然后我也不会了...

E

居然没人出。。。

F

首先注意到，每次查询有 50+% 的正确率。

easy：三分。我们将序列分成 LMR 三段，每次查询 25 次 L 和 M 的关系，25 次 M 和 R 的关系，然后就可以确定在 \(L, R, M\) 中的哪一个，4 次就可以找到了。

hard：不会……

题解：我的理解是每次随机比较任意 83 枚与 83 枚，最后枚举那个是答案，用概率最大的？ @dyh 你怎么看……我都不好说什么了。

G

参见 Keshavarz-Kohjerdi, Fatemeh, Alireza Bagheri, and Asghar Asgharian-Sardroud. ”A linear-time algorithm for the longest path problem in rectangular grid graphs.” Discrete Applied Mathematics 160.3 (2012): 210-217.

呵呵呵呵呵呵

H

看了半天的 pdf 没找到答案啊……

easy：看网页源代码去 - -

hard：看 response header. 随便设置个包含 chocolate 的 cookie 发送过去，然后就会有一个问题，然后再发送一个 request ，修改 request header 使之包含答案，然后 response 里面就有答案了。

I

。。。

J

easy：xlk 如是说：由于 NAND gate 是 unversal unary gates ，J1。。随便取两个变量 与非 或者是 或非 ，然后就有六种了。然后看xy一不一样，如果一样返回xz的与非，否则随便返回一个。

hard：我想了一下，似乎可以直接爆搜所有函数？想起来都觉得好麻烦啊 >__<

题解如是说：不满足以下五个条件中的任意一个的函数就是 universal 的：

1. 如果输入全是 1 那么输出 1
2. 如果输入全是 0 那么输出 0
3. 如果把某个输入的 0 改为 1 ，则输出的结果不会由 1 变为 0
4. 如果把所有输入取反，那么结果也会取反
5. 每个输入要么总与输出相关，要么总与输出无关

K

easy：分开计算，直接乘起来。

hard：直接考虑下来的一步，如果这一步有 1 个格子，则上去有 1 种方案；有两个格子，则上去有 2 种方案；etc。然后还是递推一下就好。

L

easy：手玩吧哈哈哈哈

hard：不会……

我居然没去看看 hard 的形状，罪过罪过。

这就是个 3-SAT 问题啊……然后自己写个程序爆搜或者直接找第三方程序吧。

我以前一直很喜欢玩这种东西的啊，居然没发现 >__<

M

不会

problem 在此

根据 \(E(\sum X_i) = \sum E(X_i)\) 可以知道答案就是每个格子为白色格子的期望和。

对于第 \(1 \leq i \leq n\) 个格子，我们知道某次被翻转的几率是 \[p = \frac{2 i (n + 1 - i) - 1}{n^2}\]

令 \(f_k\) 表示 \(k\) 次翻转后仍然是白色的概率，可以得到 \[f_0 = 0, f_{k+1} = (1 - p) f_k + p (1- f_k)\] 可以化出 \[f_{k+1}- \frac{1}{2} = (1 - 2p) (f_k - \frac{1}{2})\] 于是有 \[f_k = \frac{1}{2}(1 + (1 - 2p)^k)\]

如果暴力做的复杂度是 \(O(10^{10} \log 4000)\) 。然后一个很小的优化是如果 \(1 - 2p \leq 0.99\) ，那么 \((1 - 2p)^k \leq 10^{-18}\) ，直接忽略不计了……

然后要跑 3min 才跑得出来。

如果有更好的做法求告诉我 >__<

（版面不够了于是只好用 display equation 来充版面么 LOL）

说好的 AFK 呢，还是忍不住参加了。

Solution

250 pts

慢慢码代码。不多说。

500 pts

考虑一条边 Ai-Bj 对答案的贡献。显然它一定会在一个环上，而且环的形状一定是 Ai --- At - Bs --- Bj ，可以得到 |Ai --- At| + |Bs --- Bj| = K - 2 。

然后枚举 \(i\) ，枚举 \(j\) ，统计所有到 \(i\) 距离为 \(a\) 的点数目为 \(cnt1_a\) ，统计所有到 j 距离为 b 的点数目为 \(cnt2_b\) 。那么 Ai - bj 对答案的贡献为 \(\sum_{a+b = K-2} cnt1_a cnt2_b\) 。

注意到一个环被算两次，除个 2 就好。

900 pts

由于每一列至多只能进行一种操作，所以我们 \(2^m\) 枚举每一列只允许哪一种操作。

假如我们知道了第一行的每个操作，那么我们可以依次推出剩下的每个格子的操作，因为第二行的操作要满足第一行的结果为 B ，所以第一行的操作也确定了，依次递推下去，可以知道后面每行的操作。我们只需要验证最后一行是否仍然满足要求即可。

所以在 \(2^m\) 枚举每一列允许哪种操作后，再枚举第一行每个操作。如果这里再 \(O(2^m)\) 枚举显然会 T 。考虑到这些操作应该是同一种操作，所以进行操作的若干个格子一定是进行同一种操作的若干个格子，我们只需要枚举两个集合的子集就好了。

总时间复杂度为 \(O(nm 3^m)\) 。

nonsense

一进来看到一个 ID 为 just.for.fun 。一看是 NFLS 的，但是不知道是谁。看命名风格有点像 blue.boy ，最后发现果然是 JZP 。亚历山大 >_<

最后 room #2, #1 显然是 just.for.fun 。

Division #33 涨了 rating 。这真是极好的。