A.回文
考虑一个串满足要求会是怎样的，他通过左-shift 可以变成一个回文串，等价于一个回文串通过右-shift 可以变成这个串，那么我们手玩可以发现要么这个串本身就是回文串，要么就是两个回文串且其中有一个长度是偶数拼起来的。首先第一个就不用说了显然满足，第二个的话可以这样想：
假设我把右边 \(x\) 个 shift 过来，那么因为左 \(x\) 和右 \(x\) 个是互反的，那么我把它 shift 过来就相当于是把一个串和他的反串拼起来，那么显然是回文的。
然后再看如果两个都是奇数，因为你拼过来的左边的那个串是左 \(x\) 和右 \(x\) 长度一定是个偶数，所以一定有个偶数。
知道了哪些串可以变过来我们在看分别可以有多少个 q：
- 长度为偶数的回文串有两个 q，分别是 \(0\) 和 \(|S|/2\)
- 长度为奇数的回文串有一个 q，是 \(0\)
AB (A,B为回文)时： - \(|A|,|B|\) 中有一个偶数，有一个 q，是 \(|A|/2\) 或者\(|A|+|B|-|B|/2\) (视情况而定)
- \(|A|,|B|\) 都是偶数，有两个 q，分别是 \(|A|/2,|A|+|B|-|B|/2\)
这样的话我们计算 fi_ou,fi_ji,ed_ou,ed_ji 表示以 i 开头/结尾的长度为偶数/奇数的回文串个数就可以直接计算了
至于怎么计算这些数组的话我们就枚举中心点然后二分半径做一下差分即可
B.连通性
令 \(f_{i,j}\) 表示前 \(i\) 个点可达 \(j\) 个点的概率。
首先有 \(f_{1,1}=1,f_{i,0}=0\)，其中 \(1 \leq i \leq n\)。
接着考虑转移：
如果 \(i\) 可达，\(f_{i-1,j-1} \times (1-(1-p)^{j-1}) \to f_{i,j}\)
如果 \(i\) 不可达，\(f_{i-1,j} \times (1-p)^{j} \to f_{i,j}\)
答案即为 \(\sum_{i=1}^n f_{n,i} \times i\)
C.子区间
看起来就非常不友好。
偶数是好做的，我们随机复值一下然后做个前缀 \(xor\) 每次 \(count\) 一下即可。
如何转化？
我们把每种数第一个出现的地方扣掉就可以了！
如何维护？
从后往前扫，每一次扫到一个数的时候就把上一个这种数加进来即可，可是加数看起来很难，怎么办？
我会分块！
观察到每一次做的时候都是对一个后缀去做，那么我就分块一下，对于后面的整块记一下 \(tag\) 即可，对于当前块暴力更新即可。
真的难写！