帖子公开得有点晚。

可以说很失败。

开场看A，感觉二分代码有点奇怪，不知道题目有没问题，就去看B。

B一眼想到一种做法，每个数建一个点，相等的放同一层，得到一个分层图，问有多少种连边方案使得图是一条链。看了下 $n\le 30000$，相同的数不超过 $100$ 个，也就是每层不超过 $100$ 个点，觉得挺靠谱。

然后就开始推，结果被细节恶心到了。我的想法是按一层一层顺序把边加进去，状态 $f(i,j)$ 记前 $i$ 层构成 $j$ 条链的方案数。然而是链不是环，还得记前 $i$ 层有没包含起点和终点，于是搞了个这个玩意：$f(i,j,s,t)$。

然后思博了，中间填边的时候，我以为给 $j$ 条链每条确定一个前继节点一个后继节点就行了，然后发现有环，接着就懵逼了好长时间。

想了好几种解决方法，可惜都是错的。

于是回头看A，看了讨论知道二分代码没错，那一定是我理解错了，我平时的二分习惯相当于代码里面的 $l$ 减掉 $1$，$r$ 加上 $1$ 的。

这样就好理解了。然后又想错了，一开始想到把二分结构的线段树建出来然后DP，发现线段树的节点长度只有 $O(\log n)$ 种，准备写个STL的 map 来大力DP一波。

于是开始写转移，写着写着突然发现不妙，题目求的是 $r=k$ 的概率，我连我要求啥都没搞清楚，靠。

然后继续想，发现DP只有一条路走下去，那就只要乘法原理就行了，没必要DP。接着写完主过程发现要求 $n!$，然而 $n\le 10^9$……

打表大法好，把 $(10^7i)!$ 打出来就做完了。终于在21:30左右过了A。

再去看C，这种题似曾相识的感觉（用myy的话说就是deja vu），好像强上笛卡尔树就行。然而我并不知道两个序列的笛卡尔树怎么弄。

就YY了一个分治算法，$f(l,r)$ 求 $[l,r]$ 内的满足条件的区间个数，如果 $[l,r]$ 内 $A$ 的最大值不等于 $B$ 的最大值，沿着大的那个分成两个区间递归下去，否则，设两个最大值在 $i,j$ 位置（$i < j$），那么 $l\le i,j\le r$ 的 $[l,r]$ 都满足条件，然后加上 $f(l,j-1)+f(i+1,r)-f(i+1,j-1)$，递归下去算。

以为很靠谱，然后准备写，写前想想这玩意儿复杂度是个什么东东。——糟糕，炸了。

如果 $i$ 很接近 $l$，$j$ 很接近 $r$，那么序列长度没啥变化，大概按 $T(n)=3T(n-1)$ 估计，变成指数级算法了，比暴力还辣鸡，靠。

重新想，觉得只要构 $A$ 的笛卡尔树，然后对每个 $i$ 考虑 $A$ 中以 $A_i$ 为最大值的区间（即 $i$ 子树内的区间）中合法的个数。分析了一会儿意识到并不复杂，只要在 $B$ 中找到 $i$ 左右第一个大于等于 $A_i$ 及大于 $A_i$ 的 $B_j$ 就能求出答案，单调栈上二分一下？

不久把C搞出来了，22:20。看了一会儿后面的题，觉得E的 $b-a\le 10^8$ 好像是区间长度相关的算法，写了一个区间筛，光荣TLE。别的题也没啥思路。

接着想再折腾一下B，然而太迟了= =就先回去睡觉了。睡觉时继续脑补怎么fix这个算法。

第二天起来继续刚B，注意到左边每条链有两条边连向右边的点，那就等价于在右边连一条边，这样 $a$ 个点连 $j$ 条边就是把 $a$ 个点排列成 $a-j$ 个序列，就可以转移了。但还是怀疑想复杂了，B题为什么这么麻烦。

看到排行榜已经有10个人AK了，心灰意冷。

然而由于起点和终点的限制很麻烦，还是写了很久。

写完调样例也调了很久，发现我的DP对 $s,t$ 考虑是错的，变成起点和终点产生以后不会再和其它路径合并，然后就改。改完以后过了样例。

运气不错，交上去直接过了。然而还是怀疑把题做复杂掉了，代码比较长。

这时候大概10点，去做D了。

一开始思路挺对，把式子推了一会儿，发现有规律，有的项消掉了，最后剩下几个 $\sum_{i=0}^n{n\choose i}i^{k}$ 形式的东西。凭借经验判断这是 $2^n$ 乘一个 $k$ 次多项式，但这个多项式并不会求。。。插值？

接着就一直往插值方向去想，发现我把一个点值求出来都要至少 $O(n)$，求 $O(k)$ 个点值完全没救。优化的话，想到FFT，但是过不了，就扔了。

把表打出来看规律，发现次数不超过 $3$ 的规律很明显，次数一超过 $3$ 就各种鬼畜。联想到xumingkuan的互测题（我这题得分全场倒数），感觉不会又是什么黑科技题吧，反正没搞出来，GG。

中午吃饭的时候，突然想到——

诶，模数 $m$ 不是 $10^6$ 级别吗？

诶，答案不是关于 $n$ 的多项式吗？

把 $n$ 对 $m$ 取模就行了？

吃完饭就开始写，也没去优化log，写完过了样例就交，结果WA一块TLE一块的。TLE是复杂度不对，WA呢？

和暴力拍了拍，发现跑出来的结果不一样，然后把暴力的 $n$ 也模 $m$，一样了……

莫非是结论错了？？这时候我突然想到答案不是 $n$ 的多项式而是 $2^n$ 乘一个关于 $n$ 的多项式。。。那就判一判呗。

12:20，D过了。

看了下E和F，好像F比较可搞？就先去做F了。

嗯，我比较傻逼，果然一开始想歪了。

一开始想DP发现状态怎么记都要状压，没救。然后分析性质，一个区间翻两次肯定不优，那就只能翻一次，用 $x_{l,r}$ 表示 $[l,r]$ 这个区间翻的次数。则最后 $i$ 点被翻的次数奇偶性就是 $\sum_{l\le i}\sum_{r\ge i}x_{l,r}\bmod 2$。

如果用 $y_{i,j}$ 表示 $\sum_{l\le i}\sum_{r\ge j}x_{l,r}\bmod 2$，那么 $x_{i,j}=y_{i,j}\oplus y_{i,j-1}\oplus y_{i-1,j}\oplus y_{i-1,j-1}$，这东西如果是1就要花费代价。

好像可以最小割建图。

然后就开始想4个变量怎么建图。2个的话很简单，4个能不能先把某3个捆绑在一起？试了试，根本建不出表示与关系的图。

又想能不能设置边权满足条件，也弄不清楚。以及想到把点染色来做，然而不起作用。

想了2h+，觉得实在没救。回过头来再分析一下什么条件没用上。

嗯，如果翻转 $[a,b]$ 和 $[a,c]$，效果就相当于翻转 $[b+1,c]$。如果把差分搞出来，消掉两个差分相当于找一条最短路？想到BZOJ3003。

这样就变成求差分之间的最大权匹配，mdzz一般图最大权匹配真的可写？反正我写不出来。

不过为了AC，我还是从UOJ上抠了个带花树板子下来改了改。于是就把F题过了。

最后是E。

由于区间筛法根本做不了，索性把 $b-a\le 10^8$ 这一辣鸡条件扔了。

接着继续作大死，一开始想用筛法函数做，然后果然出问题了，一个数被小于等于 $p$ 的数筛掉不代表这个数不含大于 $p$ 的质因数。然后想到反着筛，似乎是对的。当时我还没想过复杂度是多少，觉得预处理几个东西就能做了。

然后。。。

写写写，调调调，好不容易调对了。一交，TLE得乱七八糟。

又调了一会儿。

突然意识到有一个DP第二维会爆炸！复杂度不是 $O(n^\frac{3}{4}\log^{-1}n)$ 的！

惨啊！重新推重新推。

接着的思路是统计 $[1,n]$ 以内只包含 $p$ 以内质因数的整数个数，用 $[1,b]$ 减去 $[1,a-1]$ 即可。记 $f(n,m)$ 为 $[1,n]$ 内只包含 $[m,p]$ 以内质因数的整数个数，然后DP一波……？

第二维看起来超过 $\sqrt n$ 就可以 $O(1)$ 了？这么看来就是 $O(n^\frac{3}{4}\log^{-1}n)$ 了？

写了一发交上去……

A了……

最后是22:48:19，比rank 10晚了21h+，失败告终。

51nod六题，题题掉坑。

好几题都是花了两三个小时想甚至写出来，然后出问题，把整个算法推掉重做。

A题就一乘法原理，想到奇怪的DP。

B题想太复杂了，题解有更简单的考虑方法。

C题一开始以为自己想到了很厉害的做法，想了很久才发现很爆炸。而且看了题解正解 $O(n)$，我写的是 $O(n\log n)$，还好出题人没卡= =

D题都推出是多项式了，把 $n$ 对 $m$ 取模都没想到，去想插值了……想了很久才意识到。况且 $n$ 这么大就算能插值也过不了。

E题搞了两三个小时的错误复杂度的筛法函数DP，最后才意识到是个简单的DP。看了题解好像 $b-a\le 10^8$ 这个条件还是有用的？可以记在DP状态里，当 $a=b$ 时节省状态数？

F题搞了两三个小时的网络流最小割建图，最后才意识到是类似我做过的题。

怎么说呢，尽管参加了这么多场比赛（NOIP一等奖和APIO Au都拿了两个）但我终究还是不会做题，有的题老是被第一感觉带走，然后就想歪了，回过头来一看发现是水题。。。

想题思路也不是很清楚，B题如果理清思路也并不是特别复杂。。。

以及E和F我都做过类似的题，怎么想了那么久都没意识过来正确思路。。。

总之平时太不用功，以前刷过的题并没有好好消化。。。

不过就算没掉坑也进不了前10。。。睡一觉起来就10个AK了。。。