Codeforces 1090H. Linearization

题意

定义一个长度为 $n(n=2^k,k\in N)$ 的 01 串 $s$（从 0 开始标号）是线性的，当且仅当存在整数 $x$ 和 二进制数位 $b$，使得 $\forall i\in [0,n),s_i=P(i{\rm and}x){\rm xor}b$，其中 $P(a)$ 表示 $a$ 的二进制表示中 $1$ 的数量的奇偶性

定义一个 01 串的线性化难度为，进行最少的取反一个区间的操作，使之成为线性的操作次数

给定一个长度为 $m$ 的 01 串 $t$，$q$ 次询问指定一个子串，要求计算其线性化难度

$m,q\le 2\times 10^5$

LOJ #2014. 「SCOI2016」萌萌哒

题意

有一个没有前导零的 $n$ 位十进制数 $S_1 S_2\dotsc S_n$，$m$ 条限制，一条限制形如 $S_{l_1}S_{l_1+1}\dotsc S_{r_2}$ 与 $S_{l_2}S_{l_2+1}\dotsc S_{r_2}$ 这两个子串需要完全相同

问有多少种合法的方案

模 $10^9+7$

BZOJ 2125

题意

给定 $n$个 点仙人掌（每条边只在不超过1个简单环中的无向连通图），$q$ 次询问两点间最短路

边带权

$n,q\le 10000$