由于noi.ac并没有vp的功能，我就只能自己设一个闹表，反正差别不大。
题面
T1 Nim
给定 (n)，问有多少个数组 (a_1,a_2...a_n)，满足：
- (a_iin[0,2^n))
- (a) 数组异或和非 0
- (a) 数组两两相异
(nle 10^7)，膜 (10^9+7)
T2 String
给一个 (k)。集合 (S) 中包含满足如下条件的字符串：
- 只有小写英文字母
- 相邻的字符不同
- 总共有 (k) 种不同的字符出现，出现次数分别为 (1,2...k)
再给一个 (n)，求 (S) 中字典序排第 (n) 位的串。
(kle 26,nle 10^{18})
T3 Segment
现在有一个长度为 (n) 的数组 (a)，(m) 个操作，(q) 个询问。
第 (i) 个操作用 (l_i,r_i) 描述，表示将 (a[l_i...r_i]) 中的所有数都变成这些数的最大值
现在要支持两种询问
- 单点修改 (a)
- 给定 (L,R,k)，假设 进行了区间 ([L,R]) 中的操作， (a_k) 的值是多少
(n,m,qle 10^5)，任何时刻中 (a) 数组中的所有值不会过 (10^5)。
赛时
0+10+30，几乎等同于没打。这里讲一下心路历程吧
T1 Nim
我试了好几个思路：容斥，斯特林反演+容斥，异或方程与线性方程一块解...
显然，这几个思路看起来就不是一个签到题的思路（当然，我当时并不知道这是个签到题）
另一个显然的事实是，这几个思路我都写不出来，于是我 T1 喜提 0 分的好成绩
实际上那个题就是一个简单的要死的一维递推，我居然想不出来 —— 看来是被“NOI”三个字吓住了
T2 String
我真的对这种题毫无头绪，打了10分暴力就跑了
其实后面也有想，只不过根本没有任何有效思路
T3 Segment
我一看，哇，数据结构，我会做
我一开始想了一个树套树，觉得非常对，啪啪打完了200多行，脑子一转 —— 假了
（心态 -114514）
此时我的大脑进入了空白。
冷静了一下，我想到了一个30分暴力，用了时间逆流考虑贡献的思维方法
显然我们发现最后每个位置的值，都是原来某一段连续区间中的最大值。考虑这样的一波操作，把哪些最大值给“捞”过来了。我们称这个区间为 “最大值区间”
从区间 ([k,k]) 开始，倒序遍历 ([L,R]) 中的操作，发现只有那些有交集的操作区间才影响，并且会把当前的最大值区间和这个操作区间取并集。最后我们求一下这个最大值区间的最大值就是答案了。复杂度是每次 (O(m))，即 (O(mq))
赛后
100+0+100 （不算赛时分）
T2我是真的妹懂qaq
T1 Nim
我是真没想到，这题就是一个超级傻逼的递推
设 (f(i)) 表示从 ([1,2^n)) 中选 (i) 个，各不相同，xor=0，的方案数。最后的答案就是 (inom{2^n-1}{n}n!-f(n))
设选的是 (x_1,x_2...x_{i-1},x_i)。它们的xor和得是 (0)。那 (x_i=x_1oplus x_2...x_{i-1})，考虑减去不合法的
-
(x_i=0) （因为我们不能选 (0)，所以这不合法）。
此时，前面 (i-1) 个的异或和也是 (0)， 所以它的方案数显然就是 (f_{i-1})
-
(x_i=x_k,1le k<i)。即，重复了
那这么说，前面 (i-1) 个除去 (x_k) （一共 (i-2) 个）的xor和得是 (0)。那这个方案数就是 (f_{i-2})，吗？
首先 (k) 有 (i-1) 种选法，其次 (x_k) 只需要和这 (i-2) 个不同即可，有 ((2^n-1)-(i-2)=(2^n-i+1)) 种选法。所以这个情况应该是有 ((i-1)(2^n-i+1)f_{i-2}) 种
然后，随便选 (i-1) 个不同的（确定 (x_{1...i-1})），方案数就是排列数（下降幂） (=(2^n-1)^{underline {i-1}})
于是我们得到递推：
然后这个下降幂可以一块递推，(2^n) 也可以一块递推，就可以严格线性的搞掉它。
T3 Segment
上面那个东西已经很接近正解了，我们考虑优化它
我们观察最大值区间的变化 —— 把左右端点分开观察。下面以左端点为例。
如果左端点要减小，那一定是找到了一个区间，使得它能够在覆盖当前区间，并且往左超出一点。换句话说，覆盖了当前区间的左端点。而且这样之后，我们的左端点会被换成另一个区间的左端点。
所以，我们可以直接 用操作区间的编号代替左端点的值。然后我们相当于每次要往前跳，跳到一个区间使得它的左端点可以覆盖当前区间的左端点，并且离的最近。然后我们不断的跳，直到不能跳为止。
脑袋转一转发现，对于同一个区间，我们跳的位置是一定的，于是我们可以用倍增来优化这个跳的过程。
那我们怎么预处理一个区间的最近的覆盖它左/右端点的区间呢？只需要按顺序枚举操作区间，然后搞一个线段树。设当前是第 (i) 个区间 ([l_i,r_i])，我们把 ([l_i,r_i]) 中的数都和 (i) 取 (max)。对于查询，就查询一下左端点/右端点位置上，线段树的值就行了。因为这个值相当于，“能覆盖某个位置的区间中，最大的编号”。由于我们按顺序枚举，这个“最大的编号”就相当于“离的最近”。这样就处理出了 jump[][0]。然后再倍增一下，就能得到 jump 数组了。
代码
总结
大一点讲
-
思维要发散，也要有可写性
不要搞一个不会解的方程出来，比如T1的异或/线性混合方程组
-
不要把简单问题复杂化，也不要用高级方法乱搞一通而忘记最基本的
wwq 进入直播间
wwq 把 zps 骂了一顿，说：“最基本的！最基本的都不会了！”
-
有了好想法，想着去优化，别瘫在椅子上
-
整体与个体相结合
有时我们需要看整个区间，但也需要把左右端点分开看，如 T3
有时我们需要把一个数按位拆开，但也需要看整个数，如 T1
有时我们需要把物体分开来受力分析，但也需要合在一块，排除内力，简化问题
细一点讲
- 对于 (10^7) 这样的数据，要求严格线性的那种，一般都不会涉及太难的这个那个卷积之类的，多是简单的一维递推，顶多加上一些线性筛之类的
- 对于 “假设进行了区间中的操作，...”，可以反过来考虑贡献，考虑最后的答案经历了什么过程才得到
- 对于“找最近的xxx，满足xxx条件”之类的东西，一般都可以考虑倍增解决