A
\(n\) 是奇数时恰好可以用完，\(n\) 是偶数时多出来的一块没用，所以直接输出 \((n+1)/2\) 即可。
B
每个字符出现次数都小于等于字符总数，令 \(\Sigma\) 是字符集大小，那显然有 \(|S|\le\Sigma^2\)，如果大于的话根据抽屉原理，存在一个字符出现次数大于 \(\Sigma\)，显然寄了，所以直接枚举就行，复杂度是 \(O(n\Sigma^2)\) 的。
C
做前缀和，称前缀和数组为 \(s\)，我们把 \(a\) 根据 \(0\) 划分成多段 \([l_1,r_1],[l_2,r_2], \cdots, [l_k,r_k]\) 满足 \(a_{l_i}=0, r_i+1=l_{i+1}\)，我们可以操作所有的 \(a_{l_i}\)，相当于对整个后缀操作，那我们可以用 \(a_{l_i}, a_{l_{i+1}}\) 同时操作使得一段同时加上一个任意数，而答案是前缀和最多的 \(0\) 的个数，双指针+map统计每段内出现次数最多的数字即可，注意答案要加上 \([1,l_1-1]\) 段内 \(s\) 恰好是 \(0\) 的个数。
D
约定：对于 \(x,y\in N^{*}\)，称 \(x \subset y\) 当且仅当 \(x|y=y\)，称 \(z(x)\) 为 \(x\) 二进制末尾 \(0\) 的个数。
直接的想法是说构造一个 \(x\) 使得 \(a|b \subset x\)，并且 \(d|x\)，这样 \(a|x=b|x=x\)，满足题意。
观察题目发现 \(x<2^{60}\)，而 \((a|b) < 2^{30}\)，这启发我们直接构造 \(x=t*2^{30}+(a|b)\)，其中 \(t < 2^{30}\)，相当于把两个 \(2^{30}\) 以内的数 \(t\) 和 \(a|b\) 在二进制下拼起来，接下来考虑如何构造 \(t\)。
\(t\) 要满足的条件就是说 \(-t*2^{30} \equiv a|b \pmod d\)。
现在唯一的问题是 \(2^30\) 的逆元不一定存在，但是我们发现若 \(z(d)>z(a|b)\) 一定是无解的，因为任意的 \(z(kd) \ge z(d) > z(a|b)\)，故不存在 \(x=kd\) 且 \((a|b) \subset x\)，而对于 \(z(d)\le z(a|b)\) 的情况，我们直接把 \(2^{z(d)}\) 约掉，相当于 \(-t*2^{30-z(d)} \equiv \frac{a|b}{2^{z(d)}} \pmod {\frac{d}{2^{z(d)}}}\)，\(t \equiv -\frac{1}{2^{30-z(d)}}\frac{a|b}{2^{z(d)}} \pmod {\frac{d}{2^{z(d)}}}\)，注意其中 \({\frac{d}{2^{z(d)}}}\) 和 \(\frac{a|b}{2^{z(d)}}\) 是直接除掉的，而 \(\frac{1}{2^{30-z(d)}}\) 是 \(2^{30-z(d)}\) 在模 \({\frac{d}{2^{z(d)}}}\) 意义下的逆元。
赛时样例都没过，因为求逆元写了个 \((2^{30-z(d)})^{mod-2}\)，实际上应该是 \((2^{30-z(d)})^{\varphi(mod)-1}\)，因为 \({\frac{d}{2^{z(d)}}}\) 不一定是质数，，，，，，，比赛结束后 20 分钟才调出来，寄。
E
憨憨题，没来的及做，亏麻了。
直接建出笛卡尔树，那么显然如果 \(a,b\) 的笛卡尔树相同就是符合条件的。
考虑 dp 统计这个东西，因为 \(\sum n*m \le 10^6\)，直接设计一个 \(f_{u,i}\) 表示 \(u\) 为根子树，放入数字是 \([1,i]\) 时的方案数，考虑转移，如果位置 \(u\) 放的数字不是 \(i\)，这种情况的方案数就是 \(f_{u,i-1}\)，如果放的是 \(i\)，那么这个 \(i\) 必然是整个区间中最靠左的 \(i\)，也就是左子树只能放 \([1,i-1]\)，右子树可以放 \([1,i]\)，把这两种方案数乘起来即可。
由上得出：
具体写的时候注意下空的情况，开数组的话可以搞 \(n\) 个长度为 \(m+1\) 的 vector 之类的。
原文地址：http://www.cnblogs.com/chengchunhao/p/16887991.html
