前言：最爽的切题
AB
不讲
C
本质暴力题，预处理出 xxx 的质因数，然后对于每个质因数，按照题目意思模拟即可。
D
一眼奇偶下标要分开，所以从这个出发，观察到我们要让 1,2...,n1,2...,n1,2...,n 顺序入队，维护一个双指针 L,RL,RL,R。若当前 LLL 和 RRR 奇偶性相同，当前数字所在坐标奇偶性也要一致，反之同理。
所以归纳一下：
* nnn 为偶数，所以类似维护双指针，所以要保证 (1,2),(3,4)...(n−1,n)(1,2), (3,4) ... (n-1,n)(1,2),(3,4)...(n−1,n) 奇偶性相同才又解；
* nnn 为奇数，所以 111 一定要填 111 位置（nnn 位置同理），然后转化为偶数情况。
E
推式子。
一眼发现 beauty(t)beauty(t)beauty(t) 是恒定的，跟 0/10/10/1 块有关，简单推一下 beauty(t)=⌈c2⌉beauty(t) = \lceil \frac{c}{2} \rceilbeauty(t)=⌈2c ⌉，其中 ccc 表示 si≠si***_i \not= s_{i****i =si+1 的数量。
接下来考虑一个 ttt 的幂，记为 SSS：
S=∑1≤l≤r≤n⌈c(l,r)2⌉=∑1≤l≤r≤nc(l,r)+c(l,r) mod 22=12∑c(l,r)+12∑c(l,r) mod 2\begin{aligned} S &= \sum_{1\le l \le r \le n} \lceil \frac{c(l,r)}{2} \rceil \\ &= \sum_{1\le l \le r \le n} \frac{c(l,r) + c(l,r) \bmod 2}{2}\\ &= \frac{1}{2} \sum c(l,r)+\frac{1}{2} \sum c(l,r) \bmod 2 \end{aligned} S
=1≤l≤r≤n∑ ⌈2c(l,r) ⌉=1≤l≤r≤n∑ 2c(l,r)+c(l,r)mod2 =21 ∑c(l,r)+21 ∑c(l,r)mod2
对于前面的那个式子，记为 val1val_1val1 。我们按照 ccc 的定义思考，对于一个 si≠si***_i \not= s_{i****i =si+1 的点 iii 所产生的贡献，就是左右点的个数，即 i×(n−i)i\times (n-i)i×(n−i)，所以：
val1=∑in−1[si≠si+1]×i×(n−i)val_1 = \sum_{i}^{n-1} [s_i\not=s_{i+1}]\times i \times (n-i) val1 =i∑n−1 [si =si+1 ]×i×(n−i)
对于后面的式子，记为 val2val_2val2 。考虑到这个式子可以转化为异或的 mod 2\bmod 2mod2 移一下运算：
c(l,r)=⨁i=lr−1si⊕si+1(mod2)=sl⊕sr\begin{aligned} c(l,r) &= \bigoplus_{i=l}^{r-1} s_i \oplus s_{i+1} \pmod 2 \\ &= s_l \oplus s_r \end{aligned} c(l,r) =i=l⨁r−1 si ⊕si+1 (mod2)=sl ⊕sr
所以发现跟端点是否相同有关，当且仅当为 0/10/10/1 或者 1/01/01/0 才能产生贡献，所以得出
val2=cnt0×cnt1val_2 = cnt_0 \times cnt_1 val2 =cnt0 ×cnt1
这样这个答案就是：
Ans=val1+cnt0×cnt12Ans = \frac{val_1 + cnt_0 \times cnt_1}{2} Ans=2val1 +cnt0 ×cnt1
修改也很简单，单次影响的，O(1)O(1)O(1) 可动态更新。
F1
本质暴力题，证明一下吧。
设当前二进制数最高有效位为第 kkk 位（即最大值属于 [2k,2k+1−1][2^k, 2^{k+1}-1][2k,2k+1−1]）。
我们将数组分成两组：
* 第 kkk 位为 000 的元素，共 c0c_0c0 个；
* 第 kkk 位为 111 的元素，共 c1c_1c1 个，满足 c0+c1=nc_0 + c_1 = nc0 +c1 =n。
当两个数来自同一组时，它们的异或值第 kkk 位为 000（即 <2k< 2^k<2k）。这种数对的数量为：
(c02)+(c12)≥n(n−2)4\binom{c_0}{2} + \binom{c_1}{2} \ge \frac{n(n-2)}{4} (2c0 )+(2c1 )≥4n(n−2)
* 当 n≥6n \ge 6n≥6 时：n(n−2)4≥n\frac{n(n-2)}{4} \ge n4n(n−2) ≥n。这意味着最高位为 0 的数对数量就已经 ≥n\ge n≥n 个了。因为我们取的是前 nnn 小的数，所以新数组中的所有数最高位都必然变成了 0。即每一轮变换至少彻底消除 1 个最高位。
* 当 n=5n = 5n=5 时：最坏情况下每 2 轮也必然消除 1 个最高位。
* 当 nnn 很大时（例如 n=105n = 10^5n=105）：根据抽屉原理，前 ≈15\approx 15≈15 位相同的数对数量就已经超过 nnn 个了，仅需 2 到 3 轮数组就全变成 0 了！
数值 <230< 2^{30}<230，总共只有 30 个二进制位：
* n≥6n \ge 6n≥6 时，最多变换 30 轮；
* n=5n = 5n=5 时，最多变换 60 轮；
* 只要 max(a)==min(a)\max(a) == \min(a)max(a)==min(a)，所有元素相等，后续所有变换的数对异或全为 0，可以直接 break。
所以我们每次 O(n2)O(n^2)O(n2) 暴力更新数组，记录答案即可。
