CSP 模拟 53

T1 冒泡排序（bubble）

手玩一下发现就是对每个同余类排序。

T2 染色（color）

先考虑不删，发现颜色的相对位置不会变，缩成没有连续段之后的长度为 \(len\)，相当于选出 \(len\) 个正整数，使得他们的和是 \(n\)，方案数为 \(n-1\choose len-1\)，赛时到这里就一直在想 DP，但是不会合并，其实这个东西就是统计所有本质不同子序列，要求子序列不能有相邻相同，可以上子序列自动机，我不会，所以直接 DP，设 \(f_{i,j,k}\) 表示到 \(i\)，最后为 \(j\)，长度为 \(k\) 的子序列个数，转移使用 bitset，搞了半天原来对 \(2\) 取模是因为这个。此时做到了 \(\frac{n^3}{w}\)，写一下就会发现基本没有什么转移，只有在颜色相同时才会特殊转移一下，所以设 \(f_{i,j}\) 表示以 \(i\) 结尾，长度为 \(j\) 的子序列个数，直接转移每一位的颜色即可，其他不变，加上前缀和和 bitset 后就可以做到 \(\mathcal{O}(\frac{n^2}{w})\)。

T3 图

std 22.8K，不评价。

T4 山峦

高维前缀和，不会。