Description
题目链接：BZOJ 4245
给定一个长度为 $n$ 的序列 $a_i$，将它划分为 $m$ 段连续的区间。设第 $i$ 段的费用 $c_i$ 为该段内所有数字的异或和，则总费用为 $c_1\ \text{OR}\ c_2\ \text{OR}\cdots\ \text{OR}\ c_m$，求出总费用的最小值。
数据范围：$1\le m\le n\le 5\times 10^5$，$0\le a_i\le 10^{18}$
「Codeforces 914D」Bash and a Tough Math Puzzle
Description
题目链接：Codeforces 914D
给定一个长度为 $n$ 的数列 $a_i$ 和 $q$ 次操作，有 $2$ 种操作：
1 l r x：询问是否可以改动至多一个数使得下标在 $[l,r]$ 内的数的的 $\gcd$ 为 $x$。如果可以则输出 $\text{YES}$ 否则输出 $\text{NO}$。2 i y：将 $a_i$ 修改为 $y$。
数据范围：$1\le n\le 5\times 10^5$，$1\le q\le 4\times 10^5$，$1\le a_i\le 10^9$
「NOIP 2012」疫情控制
Description
题目链接：Luogu 1084
H 国有 $n$ 个城市由 $n−1$ 条双向道路连通成一棵树，$1$ 号城市是首都，也就是根节点。H 国的首都爆发了传染病。为了控制疫情，不让疫情扩散到边境城市（叶子节点所表示的城市），当局决定让军队在一些城市建立检查点，使得从首都到边境城市的每一条路径上都至少有一个检查点。除了首都，任何一个城市都可以建立检查点。
现在，在 H 国的一些城市中已经驻扎有军队，且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动，并在最多一个城市建立检查点。军队移动需要的时间等于经过的道路的长度 $w$。请问最少需要多少个小时才能控制疫情。注意：不同的军队可以同时移动。
数据范围：$2\le m\le n\le 5\times 10^4$，$0<w<10^9$
「BZOJ 4300」绝世好题
Description
题目链接：BZOJ 4300
给定一个长度为 $n$ 的数列 $a_i$，求 $a_i$ 的子序列 $b_i$ 的最长长度 $len$，满足 $b_i\ \text{AND}\ b_{i-1}\neq 0$（$2\le i\le len$）。
数据范围：$n\le 10^5$，$a_i\le 2\times 10^9$
「Luogu 4927」梦美与线段树
Description
题目链接：Luogu 4927
有一棵维护区间和的线段树，每个节点的权值是该节点所对应区间的元素 $a_i$ 的权值和。梦美会从这棵线段树的根节点开始游历，当她要进入子节点时，假设左右儿子的权值为 $sum_l$ 和 $sum_r$，当前节点的权值为 $sum_{cnr}$，那么梦美会以 $\frac{sum_l}{sum_{cnr}}$ 的概率进入左子树，否则进入右子树。
梦美有时会把下标在 $[l,r]$ 的序列的元素权值加上 $v$。梦美每次游历时，梦美会把经过的节点权值累加，现在她希望求出这个权值的期望。答案化成最简分数为 $\frac{p}{q}$，输出 $p\cdot q^{-1}\bmod 998244353$。
数据范围：$1\le n,m\le 10^5$，$1\le a_i,v\le 10^9$
「hihoCoder 1509」异或排序
Description
题目链接：hihoCoder 1509
给定一个长度为 $n$ 的非负整数序列 $a_i$
你需要求有多少个非负整数 $S$ 满足以下两个条件：
- $0\le S<2^{60}$
- 对于所有 $1\le i<n$，都有 $a_i\oplus S\le a_{i+1}\oplus S$（其中 $\oplus$ 为异或）
数据范围：$1\le n\le 50$，$0\le a_i<2^{60}$
「Codeforces 981D」Bookshelves
Description
题目链接：Codeforces 981D
给出 $n$ 本书，每本书有一个价值 $a_i$。将这 $n$ 本书按照顺序放到 $k$ 个书架上（连续若干本书放在一个书架上，接下来连续若干本放在下一个书架上），定义一个书架的美观程度为这个书架上所有书的价值总和，定义 $k$ 个书架的美观程度为每个书架美观程度的按位与和，求这 $k$ 个书架的最大美观程度。
数据范围：$1\le k\le n\le 50$，$0<a_i<2^{50}$
「SPOJ 4168」SQFREE - Square-free integers
Description
题目链接：SPOJ 4168
求 $n$ 以内有多少个数不能被任何一个完全平方数（除 $1$ 以外）整除。
本题 $T$ 组数据。
数据范围：$1\le T\le 100$，$1\le n\le 10^{14}$