codeforces round 750 [div2]
\(a,b,c \bmod 10\) 然后暴力。
注意如果 \(a,b,c\geq 10\) 那么模完还要加上10。
10只不过是一个大偶数。
暴力看 \(0,1\) 个数。
枚举删什么字符，然后看是否回文，回文就在两个之间添加该字符。
构造 \(b,s.t. \sum a_ib_i=0\)。
两两配对 \(b_i=a_{i+1},b_{i+1}=-a_{i}\) 即可。
考虑如果奇数的话也就差一个没有完成配对的，那么暴力钦定他和第一个配对。
这样会多出一个 \(a_1\) 。似乎可以大于 \(10^9\)。
现在我们要证明这个是对的，也就是我们并不能卡掉他。
发现两两配对的时候是可以除 \(\gcd\) 的。
那么现在我们不妨假设 \(a_i\not =a_{i+1}\) 因为反证法，如果有一对相等那么就剩下 \(n-2\) 个和这两个 \(1\)。肯定是达不到 \(10^9\) 的。
那么现在肯定有 \(n/2\) 个不等于 \(10^4\) 的，所以肯定会少 \(5\times 10^4\)所以也是不满的。
考场上没想到 dp 。
csp考第二题时也不是很会 dp。应该多练练了。
把原序列 reverse 一下，那么就是正序找连续段了。
\(\text{dp}_k(x)\) 表示现在在 \(x\) 位置是第 \(k\) 段结尾的最大可能权值。
随意前缀和优化以下就好。
先说 F1 做法。
\(\text{dp}_{t}(x)\) 表示自序列以 \(t\) 结尾，\(\text{xor} = x\)。
这其实是一个 \(a_n^2\) 大小的表。
考虑每插入一个数 \(a_i\)
\(\text{dp}_{a_i}(x)=\sum_{k\leq a_i} \text{dp}_{k}(x\text{ xor }a_i)\)。
对 \(t\) 维作前缀和，直接维护前缀和数组。
本质上在 \(\text{dp}_{t-1}(a_i\text{ xor } x)=1\) 的 \(t,x\) 出，向上刷表。
即对于 \(k\in[t,\infty]\) 的 \(\text{dp}_{k}(x)\) 赋值为 \(1\)。
还是考虑刷表，显然表的大小是 \(\mathcal{O(a_i^2)}\) 级别，现在复杂度瓶颈在找到 \(\text{dp}_{t-1}(a_i\text{ xor } x)=1\) 的位置。
考虑如果你现在有一个 \(a_i\) 而之前在 \(j\) 的位置有一个 \(a_j=a_i\) ，那么在\(a_j\) 之前出现的 \(\text{xor}\) 值显然是没有必要在转移的。
所以我们每对于一对 \(x,t\) 更新转移，以后就再也不用更新了，复杂度就是 \(\mathcal{O(a_i^2)}\) 的。
比较容易的一个题。
考虑枚举区间左端点，我们需要维护出每个质因子 \(p_i\) 第一次出现的位置能延伸的最大值的最小值。
那么我们对于每个质因子 \(p_i\) 求出每个位置能到达最远位置。
这个可以单调栈 \(\mathcal{O(m)}\) 也就是 \(\mathcal{O(n\omega(a_i))}\) 求出。
然后倒着扫这个 \(a\) 数组，维护最后出现的质因子能到最远的地方。
直接用 multiset 维护即可。