memset0 发布的文章

对于每个联通块,可以看做进出了若干次将其走完,显然可以暴力状压预处理出走 ii \in [1, k] )步将该联通块走完的方案数。题意转换为,有 n 个颜色染若干个格子,相邻两个格子不能同色,某种颜色染了的次数唯一对应一个固定权值,一种方案的权值为每种颜色分别染的次数对应的权值的连乘积。这显然可以通过二项式反演来求。

READ MORE

写于:2019-01-13 20:44

更新于:2019-03-16 11:45

二项式反演:

\begin{aligned} f_n=\sum_{i=0}^{n}(-1)^i {n \choose i} g_i &\Leftrightarrow g_n=\sum_{i=0}^{n}(-1)^i {n \choose i} f_i \\ f_n=\sum_{i=0}^{n}{n \choose i} g_i &\Leftrightarrow g_n=\sum_{i=0}^{n}(-1)^{n-i} {n \choose i} f_i \end{aligned}

READ MORE

联测的题,刚好前几天做过类似的 idea 结果就 AC 了 QAQ ...

考虑对于每个 k ,处理出 b_{1 ... n - k + 1} ,对于 b 的每个长度超过 k 的极长连续段连边,可以用调和级数证明总次数不会超过 O(n \log n) 。使用后缀数组维护,类似「优秀的拆分」,也可以直接二分。后缀数组的复杂度是 O(n \log n)

考虑连边,可以利用「萌萌哒」一题的 idea ,在倍增数组上递归合并,如果左右两边已经相同就 return 掉否则就计算到答案中。可以证明这个的复杂度是均摊 \log n 级别的。

故如果使用后缀数组 + ST 表 + 倍增并查集,复杂度为 O(n \log n \times \alpha(n)) ,可以通过此题。在 n 较小 T 较大的数据点可能因为常数原因 TLE ,可以考虑对于 n 足够小的部分 O(n^2) 暴力做。

READ MORE

被同学拉去做其他的题了咕掉了考试

假设用 f(a, b) 表示长度为 a ,有 b 个黑色珠子的且满足首位连接后没有超过 k 个连续黑色珠子的方案数,设 g(x) = f(n / x, m / x) ,可以通过 Burnside 引理证明 ans = \sum\limits_{i=1}^n g(n / \gcd(i, n))

考虑 f(a, b) 相当于求方程组

x_0 + x_1 + ... + x_{a - b} = b(0 \leq x_i \leq k, 0 \leq x_0 + x_{a - b} \leq k)

的解的个数,可以转换为生成函数

READ MORE

由于没有调查数据随机,LCP 的长度不会太大,假设为 limit 。我们可以离线出所有的询问,从左往右扫描右端点,在每个右端点用字典树维护出每个长度为 i ( i \in [1, limit] ) 的 LCP 的两个后缀中下标小的下标最大值,然后直接在上面暴力查询即可,复杂度 O((n + m) \times limit) ,取 limit = 50 可过。

READ MORE