标签 travel 下的文章
上海龙年纪行
自我从上海回来已经第不知道多少天了，这篇游记还没有写完。搁置久了，竟没了写下去的心气与墨水，只此残篇，留作我懒惰的纪念吧……
自从二零一九年在宏帆中学开始中学生涯后，寒暑假几乎全部被竞赛占据，基本告别了以往一年两度的旅行了。今年，作为竞赛生的日子平淡地结束了，适逢杨金熹以及杨母邀请，说走就走，立即买得机票直达上海！
以往我们举家旅行，都是去的西安、厦门、西藏、青海这些相对经济没有那么发达的旅游城市，这次来到魔都上海，算是一次新的体验。飞机上总是会有不谙世事的小朋友，自顾自地大声喊叫。应该说大多数小时候聒噪的孩子随着年岁的增长都会收敛个性，甚至变得沉默寡言吧。这究竟是令人悲哀还是欣喜的呢？到了上空，照例只能看见脚下的云海，阳光不甚明媚，绵白的云山也染上一些无可奈何的斑驳。
落地后我们一行三人马不停蹄赶往上海中心，在上海塔底下先胡乱吃点 M 记当作午餐，待到出来，塔尖已绕上了一圈迷雾，于是先来到外滩。天仍灰蒙蒙，对岸的东方明珠，以其银灰色的外部嵌进天空。黄浦江里飘着巡逻船与塑料袋，步道行着打扮时髦的年轻人，身后矗立着建筑群，巴洛克式的，装饰艺术风格的，各国各派的风情，融在这一带了。晚上灯亮的一瞬间，外滩便换了新衣了。黑色的面料打底，橘黄的各式花纹点缀，灵动如少女。强风拂面，吹不走行人的欢欣。整条街游动起来，灯光就成了这条黄浦江旁卧着的大鱼身上的鎏金。
翌日早晨，吃的汤面做早餐。说是汤面，还真只是汤和面，里面再敷衍地放个煎蛋和肉排。几个组成成分之间没有联系，倒不如端上一碗清汤，挑几根素面，再另用盘子盛了蛋与肉。味道自然是合格的，不过对于我这个从小吃面的“面嘴子”，这种面食不足叫我称奇罢了。饭后骑共享自行车前往复旦大学。幸好路程不长，上海的低温对于裸露的双手比起刀锋只有更锋利，多待一会儿都是折磨。沿路风景比起旅游区商业街更朴素些，都是些老式居民楼，不过窗户伸出晾衣框，倒是以往没见过的稀奇景色。
复旦大学里的行道树诚然是一道风景，只是季节不作美，我只看到了秃噜枝杆的老头树。
现在我坐在徐家汇书店的一隅，敲着键盘，时而沉思，为无法流畅地写出文章而叹气。面前坐着一位尝试做寒假作业的女学生，大约写了三两字，便拿起手机翻翻寻寻；右边是一名年轻的女士，拿了《NJDTS全纪实》与 REMEMBRANDT 和一本画集，时不时看看手机，也许在查阅资料；左边又叉着二郎腿坐着一位大约四五十岁的女士，面前摆了一本簿子与一只黑笔，却一直把玩着手机。与我同行的两位，杨与杨母，坐在我的左前方与右前方，分别枕着《失乐园》与《草》小憩。这多么美妙而滑稽的一幅画卷，人人都在书店干着与书店相关而又完全不干系的事情。但若不管这么多，我又是多么希望重庆能有一家这样的书店，各类书籍琳琅满目，有这许多的原著译文对照本，这正是我需要的！重庆不是没有书店，而书店里的书大多局限了！我一直坚持不仅要读中国的书，古代的和当代的，也要读外国的书，译文和原著。在重庆的实体店很难看到带有原文对比的出版书籍，而这不论对于国语还是外语的学习，都有着莫大的帮助。从学校，尤其是中学，中学到的外语实在太局限，直击原著更能帮助人们体验与审视不同国家的、不同文化的、不同语言的美，从而建立对语言更加全面的认知。
中午吃了久违的川菜烤鱼，加了些土豆丝、拌黄瓜、煮花生、咸菜做小菜。茶尝起来十分醇厚，久品不涩舌，反而愈发酵出一味香，与重庆本地饭馆较有过之而无不及。鱼皮焦脆，辣汁吸收的很饱满，然而毕竟沪店，不很辣。肉少刺，极嫩，鲜白，伴着皮吃，焦脆与鲜嫩在口中发生奇妙的反应，与辣子味一同冲击口腔。底菜有藕片、年糕、豆皮、莴苣条，却不太相配，我以为这些应当与蒜香风味的烤鱼同行，川辣还是与血旺、白菜之类搭配更佳。
入夜前在“巧克力博物馆”点了些饮品，在店面里等着赶凌晨两点的火车。城隍庙街正是热闹的时段，人头攒动，许多小年轻自划一隅地，拍照闲谈。旧历的年底毕竟最像年底，正常开放的街道也添了几分年味，颇有几分庙会的味道。灯光橙得发黄，弥散在低温空气中，交相辉映，虽无明火，却不时叫人看见篝火的幻觉。我从未游过庙会，只在各式小说散文中耳闻。说到底，我的家乡真的搞过庙会吗？杨在店里写作业，阿姨也在自己逛街，我一人四处觅食。炸牛奶、大阪章鱼、城隍庙灌汤包、蛋仔冰淇淋，各种烧烤。吃空了钱包，填饱了肚皮。旅行这两天，肚子没有挨过饿，上顿没消化下顿又开始。既有体验美食的快乐，又有增长体重的忧伤。青春期的孩子还是比较在意体重的！只好安慰自己，待到回家，再多加运动。然而回家即过年，又要走街串巷地吃，于是先前锻炼的成果又功亏一篑，愁也！
常常说春运春运，中国的春运，世界最壮观的迁徙，却一直未尝有幸体验。这次我们没买到机票，只好乘火车，值此契机，看个究竟。火车站挤攘的人头自然不如机场里的人士看起来从容体面，目光里多藏匿着麻木与惊恐。大约我们这般平凡的水滴落入大海里，是都会被消磨了棱角与心气，不得不以最稳妥的表情示人的罢。要么疲惫的睡去，要么捧着手机，欲要看出个道理。人与人的区别与差异，个性与特征，在群体里都无限的被稀释，被消解，最后变为同一副面孔。
然而上了火车，人究竟活泼些，也就更有生机了。人群似乎总这样，乍看令人失望，而须凑近才看出几分异彩。二十九个小时的路程，的确折磨人。久坐，只觉浑身瘙痒，窗是开不了的，于是男人的气味积累起来，发酵，刺挠鼻子，再过一会儿，倒也习惯了。窗外画卷自顾自地滚动，都是看腻了的乡间景色，如钢铁巨兽般突兀地立在一群灌木中的工厂，秃噜杆的树，分割着天空的电线和屋顶摆着太阳能板的漆白的平楼，归程尚漫漫……
近日天气不好，湖北下冻雨，高速路堵塞，路旁的湖北人民不辞辛劳为高架上的人做饭烧水；高铁不能行，绿皮火车“挂帅出征”。非常时刻往往孵化莫大的感动，对于本就在绿皮上的我而言，冻雨带来的就是窗外景色的刷新，雪松尖刷上一层剔透的白，与平常的肃穆的被雪浇淋的乔木林不同，冻雨刷洗过的山林更现出妩媚的姿态，树枝凝的冰碴反射日光，晃然成五彩。
Journey -「CQOI 2021」
Day -1
Thu. & Fri. 恰逢学校运动会，于是向班主任申请了不去，然后就在机房坐着。不美好的事情可能就是文化课老师还留了这两天的作业，不过->
一旦放弃了作业，什么都好说了呢！
于是就在机房里面挑往年联考题，基本上就是在自闭中度过。
途中没有什么有意思的事情。然后就 LY & 我 & NYH 去食堂吃了饭，感叹了一下 living without fucking whk 的美好，并且做了一些神奇的讨论。
然后下午也是在联考中自闭，实在忍不住了就拉着 LY & NYH 跑去下面操场和运动会的同学们放了放风。
到了下面被 cqh 拉着玩狼人杀，玩了一局（事实上是人生的第二局狼人杀）后感觉没有什么参与感就和 LY & cq & yhr 跑到前面楼梯坐着看风景。由于当时阳光正好，看风景之人被当成风景被 zsl 照下来了。刚想跑过去抢过相机突然想起来 zsl 是班主任来着。
风景看完了 zsl 说我们不能太过于脱离集体，晚上的我校辩论赛的决赛还是和同学们一起去听，时间大约是 6:30~7:30，听完再上机房不迟。
感叹了一下 zsl 还是一个很好的班主任然后就听话地从了。
大约 6:05 的时候在教室 XF 问我为什么后面不和他们玩狼人杀了，我说我没什么参与感，然后他告诉我：“这个简单！如果你是狼人，你就说：‘我是预言家，他是狼人！’，如果你是平民，你就说：‘我是预言家，他是狼人！’，如果你是小女孩（？），你就说：‘我是预言家，他是狼人！’……”话没说完自己笑了。
晚上辩论会，和 NYH & gwy & jmy & zxy & qyy 坐在一排，这五个二年级小学生玩了至少一个多小时的真心话大冒险。
两场辩论会的主题分别是 读万卷书与行万里路孰优 和 表扬 or 批评更能促进学生进步。具体细节不太记得了，只记得第一场的反方四辩很猛，然后第二场反方四辩来了个：“在我说完我的观点后，对方辩友一定会对我的观点挑漏洞并提出批评，如果你希望我进步，你干脆就表扬我的观点算了”把孩子笑抽了。
然后两场辩论的胜者都是反方，两场四个班的最佳辩手都是四辩。果然是四辩最 NB 定律。
最特么刺激的就是辩论会 9:33 才结束，我信了你的 7:30。
Day 0
今天没什么好说的。
机房里像昨天一样哈起自闭，就中午的时候不想睡觉就干出了在机房推 gal 的壮举。
去年这个时候好像被 LJS 吐槽过。
又开始有趣起来。
下午 3:00 从学校离开去西南大学附属中学，就简称 XDFZ 吧。
我和 WJC 一个车，LY 和 NYH 一个车，在车上我才真正认识到了 WJC 的纯真本质。
然后到了 XDFZ，感觉这环境挺简陋的，不过非常亲近大自然，空气闻起来比较舒服。就是那种进去之后如果不给你讲你会觉得是一个小区的感觉。
进到科技楼感觉还是像模像样的，电脑感觉是我两届 CSP 一届 NOIP 以来见过的键盘最良心的电脑，用起来手感很正常。试机就敲了一个 NTT，然后回去过后发现错得离谱。
晚上 WJC 不知道跑哪里去了，和 LY 一起吃的守柴炉。感觉全国的守柴炉都是一个味道好神奇。
然后就回到住宿的地方。我妈定了个环境很好的民宿，荡着秋千看臧克家散文很爽。
Day 1
早上跑到 XDFZ，中途在车上看到 LYC 和 XHR，LYC 露出了强者的笑容，花花表现出了自信的神态。
到了场外没什么交流，照了个相就入场了。坐下后发密码。啊，随机串，没意思 。
打开文件夹看题目名没看出有什么奇怪的东西。然后开 PDF，只知道联赛的 BH 看到 -O2 差点感动地哭出来。
然后大约花了几分钟浏览了一遍题面，感觉题意言简意赅非常舒服，很适合我这种读题记三行的选手。
T1 感觉是个套路题，$A,B$ 拉到一起然后 two-pointers，开场半个小时就过完了所有样例加几组极限数据（伏笔）。
然后看到 T2 就萎了。啊？又来构造？NOIP 那个怎么搞的来着？freopen 输入输出成样例是吧？
冷静下来想了想，感觉 30pts 非常显，就直接 rush 了几十行又写了个 checker，大约过了 1h 过了几千组对拍。
然后先抛掉 T2，看到 T3。感觉看起来非常 函数调用，实际上基本没有关系。感觉是道不可做题，于是就打了 16pts 的裸暴力。开始看错题把 $G_{i}$ 的定义看成了删第 $i$ 条边，写了半天过不了样例。当时心里非常慌张。我确认应该是删边操作出了点问题，于是开始随机删删边加边操作。结果一不小心过了样例，仔细一读才发现原来是删 $1\sim i$。随机调试好！
回来看 T2，又开始感觉 subtask 1 的 20pts 很好拿，然后就 rush 了 285 lines，到结束都没有调出来。
中间 XDFZ 的机房还断了一次电，断了大概十分钟，然后 CCF 给我们延时延了半个小时~
出考场交流了一下，LY NYH WJC 三个貌似 T1 都是 $\mathcal{O}(m^{2})$。然后 TR LYC 是线段树二分，感觉很神。
WXK 不知道打了什么，但据他说开了 fread 极限数据从 0.9s+ 变成了 0.5s-。0.8s 的选手默默流下了不敢打 fread 的泪。
LYC T2 subtask 2 居然莽了个 flows，真是世界之大无奇不有。
出了 XDFZ 的校门，MYH 突然过来说自己 bl 了，为他默哀。
吃饭的时候用爹的手机上洛谷看了看，发现我 T1 two-pointers 好像萎了（照应），但如果运气好可能分还挺高的。不过我心态还是比较稳定的，毕竟已经被教练灌输了无数次初二来省选基本等于划水，考裂了也没什么。
然后中午酒店换成了 homeinns，和 LY 颓废，把杀手不太冷看完了。
Day 2
homeinns 的早餐挺好的，中西结合。早上出来的时候碰到了 LYC，意义不明的笑了几下。
打开题面，不会是真的吧？
看了看了 T1 的链分，也不太会，感觉可以整体二分？本着不确定的题先不管原则，我先打了 25pts 的 two-pointers 裸暴力。
这绝对是 BH 暴力最快的一次，10min 就过了所有应该过的样例，信仰不对拍。
T2 看上去一脸状压的样子，不过状压就状压为什么我的状态带进去值域连 subtask 1 都过不了？？？
哇暴搜 60pts 好香啊，于是就调了 1~2h+，终于跑过了所有样例，不过最大的跑了 20s+，信仰不对拍。
T3 感觉是个一眼题，不过 T2 调太久了只剩 1h 了，而且我也不确定还打不打得来 Tarjan，先打个 10pts 裸暴力和一个树分吧。
最后半个小时后悔了 rush 了一波 T3 正解，不过果然没调出来，就不想管了。回去检查了一堆东西，顺便看了看 T3 的树，发现有一大堆锅，赶紧修好然后测了几组数据赶紧坐正离场。
出来发现大家得分都差不多，MYH 猛汉 T1 除了正解全部写了拿了 75pts，看来是要翻盘，不愧是 DS daifan。
LYC 好像会 $\mathcal{O}(m\log^{2}_{2}n)$，顶礼膜拜。
然后就回到学校文化苦旅。
after
NYH D1T2 贪心骗过 75pts，总分 300+，为什么我考场不会贪心啊。
Journey / Solution Set - 「NOIP-S 2020」「Prob. A-C」
这种东西怎么写啊。。。
Day 1（好像也没有 Day 2
到了 NK 后发现正好可以进门，于是就什么也没有检查的进去了。
进门前问了一下 LYC 之前问过的一个问题，他说没有头绪，然后就没怎么说话了。
在去考场的途中和大 LJS 瞎扯了一下 CF 的 bitmasks 瘤子题。
小 ljs 在考场外面等的时候问我 KMP 怎么打。（伏笔 x1
我告诉他没有关系，碰见全部哈希（伏笔 x2。
快要进门的时候发现 WXK、TR、高一正在互相进行仪式。
然后就没有什么了。
进了考场之后打开 Dev，把快读之类的东西打了打，果然还是不习惯辣么大个的 Enter。
右边的右边是 WXK，坐下时互相说了句：“好巧啊”，然后互相迷惑地做了一下 orz 动作。
左边的左边是 TLY，直接 yyds。
然后，然后就发题了嘛，打开看见文件夹里一个 string 我就知道事情不对。
此时尧姐的 flag 倒了：“今年考字符串、计数我把这个键盘夹着草稿纸吃了。”
打开 PDF，先用了整整半个小时通读了一下，感觉 T1、T2 简单题，T3、T4 只能骗。
于是乎细读了一下 T1，发现是个 DFS 模拟水题。（当时没有往拓扑想，不过反正都是对的）
然后花了半个小时的样子过完了所有大样例，还很 sb 地认为不会报 int。不过保险起见还是在代码开头和考场的草稿纸（指记事本 text.txt，事实上考场上的草稿纸质量太劣我没用）都写了一句 Beware of your LONG LONG 以提醒自己最后十五分钟再重新考虑会不会爆。
然后看 T2，想了大概五分钟出了一个翻过来枚举就是 $\Theta(n\ln n)$ 大众 84pts 的垃圾做法。
此时想起了 YHN 学长在暑假的时候讲的话：“在考场上有一个暴力就先打一个，可以在正解死亡时应急以及对拍。”
然后就开始打这个 伪·$\Theta(n^{2})$。然后打出了一个 180+ 行的垃圾。
T3 带 SPJ，此时教练的 flag 倒了：“NOIP 不会考带 SPJ 的东西，以后不要考了。”
T3 又是个构造，此时教练的 flag 又倒了：“NOIP 不会考构造，以后不要考了。”
到了后面就根本不想打正解了，只想着调自己的暴力。结果就是调到后面越调越慌，连改思路的想法都没有。
最后就改了个 T1 的 long long，什么也没有干。
于是，NOIP2020 成了至暗时刻。
出来考场后，我问 LYC T2 的复杂度，他说：“$\Theta(Tn\sqrt{n})$”。我当时就以为块 YC 打了个分块。
中午大家一起到某个不知名的地方吃了一个疑似火锅的东西。
桌子上小 ljs 跟我一样 T2 陷在 $\Theta(n^2)$ 潮流中，其他人都打了 84。
然后说着说着 LYC 发现自己 T1 读错了题（后来被证实是出题人语文差，自己也没考虑这些，于是读错题 没 有 关 系），蒙着发现自己也读错了。
然后就觉得，要完，这下没了（本来就没了好吧）。
本来大家都十分快乐的对着自己的答案，然后尧姐冒了一句：“大家不要对了，伤感情。”
于是 LYC 对着这个 T12 没对出错 T34 骗分稳健的人喊了一句：“对了半天没对出错，有优越感了是吧。”
十分奇妙的，本来大家都对吃没有什么兴趣，LYC 和 LJS 这两个饭量小的早就不吃了，结果 TR 点的虾滑来之后一个二个都站了起来。
感觉就这样了吧，NOIP2020 是灰色但打醒的。
Sol.
A 排水系统
找出所有的起点 DFS 即可，可以手动实现一个分数类。
/* Beware of your __INT128 */
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
namespace MySpace {
typedef long long LL;
const __int128 MAXN = 1e5 + 5, MAXS = 10 + 5, MAXE = 1e5 + 5;
__int128 rint () {
__int128 x = 0, f = 1; char c = getchar ();
for ( ; c < '0' || c > '9'; c = getchar () ) f = ( c == '-' ? -1 : f );
for ( ; c >= '0' && c <= '9'; c = getchar () ) x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
return x * f;
}
template<typename _T>
void wint ( _T x ) {
if ( x < 0 ) putchar ( '-' ), x = ~ x + 1;
if ( x > 9 ) wint ( x / 10 );
putchar ( x % 10 + '0' );
}
__int128 calcGCD ( const __int128 a, const __int128 b ) ;
__int128 calcLCM ( const __int128 a, const __int128 b ) ;
struct GraphSet {
__int128 to, nx;
GraphSet ( __int128 T = 0, __int128 N = 0 ) { to = T, nx = N; }
} as[MAXN * 5 * 4];
struct Frac {
__int128 one, ano;
Frac ( __int128 O = 0, __int128 A = 0 ) { one = O, ano = A; }
} nds[MAXN];
__int128 n, stn, edn, bgn[MAXN], cnte, ind[MAXN], outd[MAXN], sts[MAXN], eds[MAXN], stnd, ednd, vis[MAXN];
void makeEdge ( const __int128 u, const __int128 v ) { as[++ cnte] = GraphSet ( v, bgn[u] ), bgn[u] = cnte; }
__int128 calcGCD ( const __int128 a, const __int128 b ) { return ! b ? a : calcGCD ( b, a % b ); }
__int128 calcLCM ( const __int128 a, const __int128 b ) { return ( ! a || ! b ) ? 0 : ( __int128 )a / calcGCD ( a, b ) * b; }
void getSimp ( Frac& fr ) { __int128 ret = calcGCD ( fr.one, fr.ano ); if ( ! ret ) fr = Frac (); else fr.one /= ret, fr.ano /= ret; }
void dfs ( const __int128 u ) {
for ( __int128 i = bgn[u]; i; i = as[i].nx ) {
__int128 v = as[i].to;
Frac ad = Frac ( nds[u].one, nds[u].ano * outd[u] );
getSimp ( ad );
__int128 ret = calcLCM ( ad.ano, nds[v].ano );
if ( ! ret ) nds[v] = ad, dfs ( v );
else {
__int128 ads = ret / ad.ano, us = ret / nds[v].ano;
ad.one *= ads, ad.ano *= ads;
nds[v].one *= us, nds[v].ano *= us;
nds[v].one += ad.one;
getSimp ( nds[v] );
dfs ( v );
}
}
if ( bgn[u] ) nds[u] = Frac ();
}
void Main () {
n = rint (), stn = rint ();
for ( __int128 i = 1; i <= n; ++ i ) {
__int128 eg = rint ();
for ( __int128 j = 1; j <= eg; ++ j ) {
__int128 to = rint ();
makeEdge ( i, to );
ind[to] ++, outd[i] ++;
}
}
for ( __int128 i = 1; i <= n; ++ i ) {
if ( ! ind[i] ) sts[++ stnd] = i;
if ( ! outd[i] ) eds[++ ednd] = i;
}
for ( __int128 i = 1; i <= stnd; ++ i ) nds[sts[i]].one = nds[sts[i]].ano = 1;
sort ( eds + 1, eds + 1 + ednd );
for ( __int128 i = 1; i <= stnd; ++ i ) dfs ( i );
for ( __int128 i = 1; i <= ednd; ++ i ) wint ( nds[eds[i]].one ), putchar ( ' ' ), wint ( nds[eds[i]].ano ), putchar ( '\n' );
}
}
int main () {
// freopen ( "water.in", "r", stdin );
// freopen ( "water.out", "w", stdout );
MySpace :: Main ();
return 0;
}B 字符串匹配
这里是 $\Theta(Tn\ln n+26Tn)$，我 yy 出来的一个 $\Theta(n\ln n+Tn)$ 的做法由于太过繁杂不想想了。
首先枚举 $AB$ 即循环节，然后挨个往后面跳记个数就好了。
#include <cstdio>
#include <cstring>
namespace mySpace {
typedef long long LL;
const int KEY = 1331;
const int MAXN = ( 1 << 20 ) + 5;
int mul ( const LL a, const LL b, const int p ) { return a * b % p; }
int add ( const int a, const int b, const int p ) { return ( a + b ) < p ? ( a + b ) : ( a + b - p ); }
int sub ( const int a, const int b, const int p ) { return ( a - b ) < 0 ? ( a - b + p ) : ( a - b ); }
struct Value {
static const int onemod = 19260817, anomod = 998244353;
int p, q;
Value () : p ( 0 ), q ( 0 ) {}
Value ( const int x ) : p ( x ), q ( x ) {}
Value ( const int a, const int b ) : p ( a ), q ( b ) {}
Value operator * ( const Value &other ) const { return Value ( mul ( p, other.p, onemod ), mul ( q, other.q, anomod ) ); }
Value operator + ( const Value &other ) const { return Value ( add ( p, other.p, onemod ), add ( q, other.q, anomod ) ); }
Value operator - ( const Value &other ) const { return Value ( sub ( p, other.p, onemod ), sub ( q, other.q, anomod ) ); }
bool operator == ( const Value &other ) const { return p == other.p && q == other.q; }
bool operator != ( const Value &other ) const { return ! ( Value ( p, q ) == other ); }
} pwr[MAXN], has[MAXN];
int n, mps[MAXN], buc[MAXN][26], suf[MAXN];
char str[MAXN];
void initial () {
scanf ( "%s", str + 1 ), n = strlen ( str + 1 );
for ( int i = 1; i <= n; ++ i ) mps[i] = str[i] - 'a';
bool tmp[26] = {}; int cur = 0;
for ( int i = 1; i <= n; ++ i ) {
has[i] = has[i - 1] * KEY + mps[i];
memcpy ( buc[i], buc[i - 1], sizeof ( int ) * 26 );
tmp[mps[i]] ^= 1, cur += tmp[mps[i]] ? 1 : -1;
for ( int j = cur; j < 26; ++ j ) buc[i][j] ++;
}
memset ( tmp, 0, sizeof ( tmp ) ), cur = 0;
for ( int i = n; i; -- i ) tmp[mps[i]] ^= 1, cur += tmp[mps[i]] ? 1 : -1, suf[i] = cur;
}
Value calcHS ( const int l, const int r ) { return has[r] - has[l - 1] * pwr[r - l + 1]; }
void solve () {
initial (); LL ans = 0;
for ( int len = 2; len < n; ++ len ) {
Value tmp = calcHS ( 1, len );
for ( int nxt = len; nxt < n; nxt += len ) {
if ( calcHS ( nxt - len + 1, nxt ) != tmp ) break;
ans += buc[len - 1][suf[nxt + 1]];
}
}
printf ( "%lld\n", ans );
}
void main () {
pwr[0] = 1;
for ( int i = 1; i <= MAXN - 5; ++ i ) pwr[i] = pwr[i - 1] * KEY;
int TC; scanf ( "%d", &TC );
while ( TC -- > 0 ) solve ();
}
}
int main () {
// freopen ( "string.in", "r", stdin );
// freopen ( "string.out", "w", stdout );
mySpace :: main ();
return 0;
}C 移球游戏
首先肯定这是 $n$ 个栈。先看 $n=2$ 的部分分。
这种情况只有黑白两色。
设 $1$ 柱有 $b$ （总共）个黑棋，有 $w$ 个白棋，把 $2$ 柱上 $b$ 个棋子放到 $3$ 柱上，然后重复：
- 把 $1$ 柱顶部所有黑棋放到 $2$ 柱上。
- 然后把 $1$ 柱上所有白棋放到 $3$ 柱。
直到 $1$ 柱为空。
然后把 $3$ 柱上面本属于 $1$ 柱的白棋放回去，又把 $2$ 柱上面的 $b$ 个黑棋放到 $1$ 柱去。
于是乎现在 $1$ 柱的情况大概是这样的：
假设原本是这样的：
$$ \begin{aligned} &\texttt{W W B W W B W W B B B} \\ &\texttt{W B W B B B W B W B W} \end{aligned} $$
那么现在移完后是这样：
$$ \begin{aligned} &\texttt{W W W W W W B B B B B} \\ &\texttt{W B W B B B} \\ &\texttt{W B W B W} \end{aligned} $$
然后我们把此时 $2$ 柱上的棋子全部放到 $3$ 柱上去，然后就划分一下就完了。
后面的事情就简单了，当 $n>2$ 的时候打个分治，一半一半划分染色，然后按着按着整理。
（代码和 CQ 队长 jiangly 对拍过，不过莫名奇妙就变成了基因比照，于是代码就基本变成了 jiangly 的）
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
namespace mySpace {
const int MAXN = 50 + 5, MAXM = 400 + 5, MAXK = 820000 + 5;
int rint () {
int x = 0, f = 1; char c = getchar ();
for ( ; c < '0' || c > '9'; c = getchar () ) f = c == '-' ? -1 : f;
for ( ; c >= '0' && c <= '9'; c = getchar () ) x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
return x * f;
}
template<typename _T>
void wint ( _T x ) {
if ( x < 0 ) putchar ( '-' ), x = ~ x + 1;
if ( x > 9 ) wint ( x / 10 );
putchar ( x % 10 ^ '0' );
}
struct Stack {
private:
int stk[MAXM], _top;
public:
Stack () { memset ( stk, 0, sizeof ( stk ) ), _top = 0; }
void push ( const int val ) { stk[_top ++] = val; }
void pop () { if ( _top ) _top --; }
int at ( const int pos ) { return stk[pos]; }
int top () { return stk[_top - 1]; }
int size () { return _top; }
bool empty () { return _top < 0; }
void debug ( char c = ' ' ) {
putchar ( '[' );
for ( int i = 0; i < _top; ++ i ) printf ( "%d ", stk[i] );
printf ( "]%c", c ) ;
}
} clr[MAXN];
struct Answer {
int one, ano;
Answer ( int O = 0, int A = 0 ) { one = O, ano = A; }
} ans[MAXK];
int n, m, cnt;
void trans ( const int one, const int ano ) {
clr[ano].push ( clr[one].top () );
clr[one].pop ();
ans[cnt ++] = Answer ( one, ano );
}
void solve ( const int l, const int r, const vector<int>& col ) {
if ( r - l == 1 ) return;
int mid = ( l + r ) >> 1;
int lst = col[0];
vector<int> onevec, anovec;
for ( int i = 1; i < r - l; ++ i ) {
int one = lst, ano = col[i], cnt = 0;
for ( int j = 0; j < m; ++ j ) {
if ( clr[one].at ( j ) < mid ) ++ cnt;
}
for ( int j = 0; j < cnt; ++ j ) trans ( ano, n );
for ( int j = m - 1; ~ j; -- j ) {
if ( clr[one].at ( j ) < mid ) trans ( one, ano );
else trans ( one, n );
}
for ( int j = 0; j < m - cnt; ++ j ) trans ( n, one );
for ( int j = 0; j < cnt; ++ j ) trans ( ano, one );
for ( int j = 0; j < m - cnt; ++ j ) trans ( ano, n );
for ( int j = 0; j < cnt; ++ j ) trans ( one, ano );
for ( int j = m - 1; ~ j; -- j ) {
if ( clr[ano].size () < m && ( clr[n].at ( j ) < mid || clr[one].size () == m ) ) trans ( n, ano );
else trans ( n, one );
}
bool was = 0;
for ( int j = 0; j < m; ++ j ) {
if ( clr[ano].at ( j ) >= mid ) was = 1;
}
if ( was ) anovec.push_back ( one ), lst = ano;
else onevec.push_back ( ano ), lst = one;
}
if ( clr[lst].at ( 0 ) < mid ) onevec.push_back ( lst );
else anovec.push_back ( lst );
solve ( l, mid, onevec ), solve ( mid, r, anovec );
}
void main () {
n = rint (), m = rint ();
for ( int i = 0; i < n; ++ i ) {
for ( int j = 0; j < m; ++ j ) clr[i].push ( rint () - 1 );
}
vector<int> col;
for ( int i = 0; i < n; ++ i ) col.push_back ( i );
solve ( 0, n, col );
wint ( cnt ), putchar ( '\n' );
for ( int i = 0; i < cnt; ++ i ) {
wint ( ans[i].one + 1 ), putchar ( ' ' );
wint ( ans[i].ano + 1 ), putchar ( '\n' );
}
}
}
int main () {
// freopen ( "ball.in", "r", stdin );
// freopen ( "ball.out", "w", stdout );
mySpace :: main ();
return 0;
}