大多数题解都是口胡，不保证正确性，有错请指出，谢谢。
CQOI2018
除了“交错序列”和“九连环”两道数学题以外，全是板子题，遭不住了。
-
BSGS 板子题，时间复杂度 \(\mathcal{O}(n\sqrt P\log P)\) 或 \(\mathcal{O}(n\sqrt P)\)。
-
矩阵树定理板子题，时间复杂度 \(\mathcal{O}(n^3)\)。
-
由于 \(x+y=n\) ，所以权值转化为 \((n-y)^ay^b=\sum_{i=0}^{a}(-1)^{a-i}\binom{a}{i}n^iy^{a+b-i}\) 。只需要求出一个序列的权值是 \(y^{i},i\in[a,a+b]\) 的所有答案即可。
经典的 dp ：\(f_{i,j,0/1}\) 表示长度为 \(i\) 的序列，权值是 \(y^j\) ，最后一个数是 \(0/1\) 的权值和。转移：
\[f_{i,j,0}=f_{i-1,j,0}+f_{i-1,j,1} \]\[f_{i,j,1}=\sum_{k=0}^{j}\binom{j}{k}f_{i-1,k,0} \]矩阵加速转移即可，时间复杂度 \(\mathcal{O}((a+b)^3\log n)\) 。
也可以直接枚举 1 的个数，写出最后的答案：
\[\sum_{i=0}^{\lfloor\frac{n+1}{2}\rfloor}\binom{n-i+1}{i}(n-i)^ai^b \]线性筛 \(i^a,i^b\) 即可，时间复杂度 \(\mathcal{O}(n(1+\frac{\log a+\log b}{\log n}))\) 。
洛谷题解区有人用 EI 科技做到了时间复杂度 \(\mathcal{O}(\log n+(a+b)\log (a+b))\) ，但我不会。
-
显然的状压 dp ：\(f_{i,j}\) 表示经过的点集为 \(i\) ，最后一个点是 \(j\) 的方案数。转移时枚举下一个点 \(k\)，预处理连 \((j,k)\) 需要事先经过哪些点即可。时间复杂度 \(\mathcal{O}(2^nn^2)\) ，除去无用状态后可以通过。
-
通过观察样例，可以盯出来答案是 \(\lfloor\frac{2^{n+1}}{3}\rfloor\) ，高精度计算即可，时间复杂度 \(\mathcal{O}(nm)\) 。
详细的推导过程：两个规则都是允许随意上下，那么上 \(n\) 连环和下 \(n\) 连环互为逆过程，所以上 \(n\) 连环和下 \(n\) 连环的步数是一样的。观察四连环的拆卸过程，发现整个过程可以归纳为：
\[111...11\rightarrow 11000...00\rightarrow 01000..00\rightarrow 0111...111 \rightarrow 000...00 \]也就是拆 \(n\) 连环，先拆 \(n-2\) 连环，再操作一步，在上 \(n-2\) 连环，再拆 \(n-1\) 连环。设 \(f_{n}\) 为拆 \(n\) 连环所需的步数，那么：
\[f_n=f_{n-1}+2f_{n-2}+1 \]\[f_0=0,f_1=1 \]稍微变形一下便容易得到：
\[f_n+f_{n-1}+1=2(f_{n-1}+f_{n-2}+1) \]\[f_n+f_{n-1}=2^n-1 \]\[f_n=f_{n-2}+2^{n-1} \]分奇偶讨论一下即可得到结论。
-
区间异或和转化成前缀异或和后就可以直接莫队了，时间复杂度 \(\mathcal{O}(n\sqrt m)\) 。
AHOI2018初中组
虽然是初中组，但整体思维难度比 CQOI 高。“根式化简”需要发现 \(x^\frac{1}{4}\) 的特殊性质；“分组”的原题是简单的贪心，加强版是经典套路；“球球的排列”通过经典的转化后变成经典的计数问题。
-
同题目名字，签到题，答案为 \(\sum_{i=1}^{n-1}\max(a_i,a_{i+1})\)
-
显然 \(a\le x^{\frac{1}{3}}\) ，但直接 \(\mathcal{O}(n(\frac{x^\frac{1}{3}}{\log x}+\log x))\) 并不能过。再进一步观察，可以发现把所有小于等于 \(x^{\frac{1}{4}}\) 的质数都尝试了之后，剩下的未被分解的 \(x'\) 要么是一个完全立方数（并且形如 \(p^3\) ，\(p\) 是质数），要么不含立方因子。所以提前处理一个所有小于等于 \(x^\frac{1}{3}\) 的质数的立方表，在上面二分查找一下即可，时间复杂度 \(\mathcal{O}(n(\frac{x^\frac{1}{4}}{\log x}+\log x))\)
-
排序后贪心地模拟分组情况就好了，优先把当前的人加到之前人数最小的组里，剩余的没分配到的组就抛弃掉，开个队列维护就好。时间复杂度 \(\mathcal{O}(n\log n)\) 。
值得注意的是（其实就是我读错题了），此题不需要满足分组在原序列连续。如果加了这个限制的话，可以二分答案后，用单调栈加线段树维护 dp 可以转移的所有位置来快速计算 dp 值，时间复杂度 \(\mathcal{O}(n\log^2n)\) ，因为跟此题关系不大，不详细叙述。
-
经典题。把所有数的平方因子去掉之后，问题转化成每个元素有一个颜色，问有多少排列满足相邻元素颜色不同。\(\mathcal{O}(n^3)\) 做法大概就是按颜色依次插入球，然后 dp：\(f_{i,j,k}\) 表示当前插入第 \(i\) 个球，之前的颜色里，相邻的有 \(j\) 对，当前的颜色里，相邻的有 \(k\) 对的方案数。转移时分类讨论即可。
然而这个问题有熟知的 \(\mathcal{O}(n\log^2n)\) 做法。以下认为颜色相同的球没有区别，最后方案数乘一些阶乘就好了。设恰好有 \(i\) 对相邻球颜色相同的排列个数为 \(G_i\) ，至少有 \(i\) 对相邻球颜色相同的排列个数为 \(F_i\) ，由二项式反演：
\[F_i=\sum_{j=i}^{n-1}\binom{n-1}{j}G_j \]\[G_i=\sum_{j=i}^{n-1}(-1)^{j-i}\binom{n-1}{j}F_j \]下面求 \(F\) 。记 \(m\) 为颜色种类数， \(c_i\) 的为第 \(i\) 种球的个数，设 \(h_{i,j}\) 为把第 \(i\) 种球分成若干个连续段，其中相邻的球有 \(j\) 组的方案数，\(\hat H_i(z)\) 为 \(h_i\) 的 EGF。那么容易得到 \(\hat H_i(z)=\sum\limits_{j=0}^{c_i-1}\frac{\binom{c_i-1}{j}z^j}{j!}\) 。所以 \(F_i=n![z^i]\prod\limits_{i=1}^{m} H_i(z)\)，分治 NTT 计算即可。
HNOI/AHOI2018
-
一个经典的结论是某一位最后是 0/1 取决于最后一次 "&0"/"|1"，其他操作对值不产生任何影响。有这个结论之后，还可以构造出一个更强的结论：对某一位 \(i\) 来说，记它的所有操作于它的值拼接而成的二进制表示为 \(b_i\)，低位为先操作的值，高位为后操作的值。令 & 为 1，| 为 0 ，那么每种插入的运算符方案也对应一个二进制数 \(x\) ，高低位同上。那么，第 \(i\) 位最后的结果是 1 当且仅当 \(x<b_i\) 。这个结论是不难证明的。所以可以先对于每一位的二进制数基数排序一下，查询的时候找到所有 1 的位的最小的数 \(x\) 和所有 0 的位的最大的数 \(y\) ，答案即为 \(\max(y-x,0)\) 。