ARC150
不妨把每个点看作 A i A_i Ai，那么一条路径就是经过点的 A i A_i Ai构成的序列。记 d i d_i di表示 1 → i 1\to i 1→i路径构成的所有序列中与 B B B序列 L C S LCS LCS的最小值（必须是 B B B序列的前缀）。只需判断 d n = K d_n=K dn=K。
转移类比 LCS \text{LCS} LCS。事实上这是 L C S LCS LCS在无向图中的形式 。那么 d i = min ( d j + [ B d j + 1 = A i ] ) d_i=\min(d_j+[B_{d_j+1}=A_i]) di=min(dj+[Bdj+1=Ai])。只需每次取出 d i d_i di最小的节点拓展。跑 dijkstra \text{dijkstra} dijkstra即可。
#include记 v i v_i vi表示节点 i i i被操作的期望次数。答案是 ∑ i = 1 n v i \sum_{i=1}^nv_i ∑i=1nvi。
感性理解一下，此时只需考虑发生在路径 1 → i 1\to i 1→i上的操作。问题转述为每次从 i i i个点中随机选一个，所有点都被选中时 i i i节点的操作次数（注意如果操作的是好的点也算，相当于样本容量变大了，但是期望不变）。注意到 i i i个节点的操作次数应该是相等的，因此只需算总操作次数，也就是 ∑ j = 1 i i j \sum_{j=1}^i\frac{i}{j} ∑j=1iji。只需预处理 ∑ j = 1 i 1 j \sum_{j=1}^i\frac{1}{j} ∑j=1ij1即可。
#include思维题。非常考验观察能力。
记 f i f_i fi表示 1 ∼ i 1\sim i 1∼i中 R R R的数目减去 L L L的数目。不妨假设 R R R的总数目大于 L L L的总数目（反之将原串翻转并取反即可），那么 f n k > 0 f_{nk}>0 fnk>0。
那么 S i S_i Si反转的情况为：
1.1
1.1
1.1
S
i
=
L
S_i=L
Si=L ，并且
f
i
≥
0
f_i\ge0
fi≥0
1.2
1.2
1.2
S
i
=
R
S_i=R
Si=R，并且
f
n
k
−
f
i
<
0
f_{nk}-f_i<0
fnk−fi<0 。稍作变形得到
f
i
>
f
n
k
f_i>f_{nk}
fi>fnk
不难发现对于直线 y = f n k y=f_{nk} y=fnk上方的边都会被反转，包括一些满足 f i ≥ 0 f_i\ge 0 fi≥0的下降边。
并且一次操作后， f n k f_{nk} fnk成为最大值，这意味着只会存在往上翻而不会存在往下翻的情况。只要存在 y = 0 y=0 y=0上方的下降边就会被翻上去，因此最终所有边都会被翻上去，只有 y = 0 y=0 y=0下方的前缀能存活。
模拟即可。复杂度 O ( n ) O(n) O(n)。
#includeARC151
B题还要想半天。
假设第i位时第一次出现不同。可以得到如下限制：
a 1 = a p 1 , a 2 = a p 2 , . . . , a i − 1 = a p i − 1 , a i ≠ a p i a_1=a_{p_1},a_2=a_{p_2},...,a_{i-1}=a_{p_{i-1}},a_i\ne a_{p_i} a1=ap1,a2=ap2,...,ai−1=api−1,ai=api
如果在图论中来看的话，首先 i i i和 p i p_i pi不在同一连通块，其次如果有 k k k个连通块，那么方案数 m k − m k − 1 2 \frac{m^k-m^{k-1}}{2} 2mk−mk−1
复杂度 O ( n log n ) O(n\log n) O(nlogn)。
#include前置知识： S G SG SG函数。
可以把每个状态视为一个节点，再从每个状态向它的后继状态连边，定义 S G ( x ) = mex ( S G ( y 1 ) , S G ( y 2 ) , . . . , S G ( y k ) ) SG(x)=\text{mex}(SG(y_1),SG(y_2),...,SG(y_k)) SG(x)=mex(SG(y1),SG(y2),...,SG(yk))。显然当 S G ( x ) = 0 SG(x)=0 SG(x)=0时必败， S G ( x ) ≠ 0 SG(x)\ne 0 SG(x)=0时必胜。
一般的，如果由 n n n个有向图游戏组成，那么必胜的充要条件是 ⊕ i = 1 n S G ( x i ) ≠ 0 \oplus_{i=1}^nSG(x_i)\ne 0 ⊕i=1nSG(xi)=0 。
道理很简单。 S G ( x i ) SG(x_i) SG(xi)向 S G SG SG函数大的方向转移是无效的（因为可以被转移回来），因此 S G ( x i ) SG(x_i) SG(xi)只能转移到 0 ∼ S G ( x i ) − 1 0\sim SG(x_i)-1 0∼SG(xi)−1，而这和 n i m nim nim游戏类似，最终所有 S G ( x i ) SG(x_i) SG(xi)都变成 0 0 0，也就是都不能操作的情况。
思考：如何求 S G ( x 1 , x 2 , . . . , x n ) SG(x_1,x_2,...,x_n) SG(x1,x2,...,xn)?
应该可以感性认识到就是 ⊕ i = 1 n S G ( x i ) \oplus_{i=1}^nSG(x_i) ⊕i=1nSG(xi)。因为是yy的所以没有证明。
考虑如何运用。显然每一个空白段构成一个有向图游戏，只需分析每个空白段的 S G SG SG。
首先一个观察：最终不能操作的局面一定是 01 01 01交错，也就是说如果初始状态是 01 01 01交错的那么必败。
因此如果两端相同那么必胜，如果两端不同那么必败。
如果只有一端有值，假设是 1 1 1，不妨设长度为 n n n，考虑填一个 0 0 0在中间，那么 mex ( ∑ i = 0 n − 1 i ⊕ 0 ) = n \text{mex}(\sum_{i=0}^{n-1}i\oplus 0)=n mex(∑i=0n−1i⊕0)=n。
因此计算每一段 S G SG SG值即可。
#include纯纯的人类智慧。
考虑对操作序列进行调整。我们注意到，如果 X i ≠ X i + 1 X_i\ne X_{i+1} Xi=Xi+1，那么交换 i i i和 i + 1 i+1 i+1的操作顺序不会影响结果。
道理很简单。每次操作 i i i最多有两条转移路径，即 i → i i\to i i→i 以及 i → i ⊕ 2 a i\to i\oplus2^a i→i⊕2a。也就是说 i i i只会转移到 { i , i ⊕ 2 a , i ⊕ 2 b , i ⊕ 2 a ⊕ 2 b } \{i,i\oplus 2^{a},i\oplus 2^b,i\oplus 2^a\oplus 2^b\} {i,i⊕2a,i⊕2b,i⊕2a⊕2b} ( a ≠ b ) (a\ne b) (a=b)。不难验证它是正确的。
据此，我们可以很自然地想到对于相同的 X i X_i Xi一起处理。而我们发现这样的转移可以通过两两分组来实现，其过程是平凡的线性递推关系，直接乘转移矩阵即可。
时间复杂度 O ( n 2 n + Q ) O(n2^n+Q) O(n2n+Q)。
总结：对递推关系的考察。
我信仰什么，我便实现哪种方法。
#include