写于：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}

- 阅读剩余部分 -

联测的题，刚好前几天做过类似的 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) 暴力做。

- 阅读剩余部分 -

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

假设用 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)

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

- 阅读剩余部分 -

  1. 1
  2. 2
  3. 3
  4. 4
  5. ...
  6. 9