被 mwh 嘲讽：「你会 SAM 吗，你不是什么题都写 SA 的吗」 于是自己想出来了这题

考虑根号分治，对于一组查询 (l, r, k) ，我们先将其拆成 (1, r, k) - (1, l - 1, k) 。

若 length[k] > \sqrt n 考虑这样的 k 不会超过 \sqrt n 个，对于每个都在 SAM 上暴力 DFS 统计出每个形如 (1, i, k), i \in [1, n] 的答案，时间复杂度 O(n \sqrt n) 。

若 length[k] \leq \sqrt n 考虑先把所有 (1, i, k) 按照 i 从小到大排序。i 对 j 产生贡献当且仅当 i 在 SAM 上的结束节点时 j 在 SAM 上某个节点的祖先。考虑扫描线，每次插入一个串就将其子树增加 1 ，每查询一个串就暴力遍历在 SAM 上的每个点查询，由于串的长度 \leq \sqrt n ，所以单个询问最多查询 \sqrt n 次。

如果使用线段树状物来维护子树的修改，时间复杂度是 O(n \sqrt n \log n) 的。考虑到修改只有 O(n) 次而询问有 O(n \sqrt n) 次，可以考虑使用 O(\sqrt n) 修改，O(1) 查询的分块来解决。

READ MORE

还记得去年去打这个比赛的时候是人生第一次 ACM ... 那是还是普及选手，被 mwh 和 wxw 爆踩。

时间过的好快啊，没想到转眼又是一年过去了诶 ... 仿佛去年来的时候，记忆还是那么的清晰呢 ...

那么 ... 按照惯例，来写流水账了~

READ MORE

对于两棵树 T_1, T_2，定义它们的交 T_1 \cap T_2 是它们的边集的交形成的森林，k(T_1 \cap T_2)表示这个森林的连通块个数，求下列三种问题之一：

  1. 给定 T_1, T_2，求 y^{k(T_1\cap T_2)}

  2. 给定 T_1，求 \sum_{T_2}y^{k(T_1\cap T_2)}

  3. 给定 n，求 \sum_{T_1}\sum_{T_2}y^{k(T_1\cap T_2)}

其中 n \leq 10^5 ，上面的 sum 是对所有 n^{n-2} 种可能的树求和。答案对 998244353 取模。

orzrqy

READ MORE

先看 n=1 的情况，考虑令 a = w_{1, 1} ，用 f_i 表示跳了 i 步的答案，则 f_i = a^i \binom n i 。

考虑

\begin{aligned} ans &= \sum_{i \bmod k=m} f_i = \sum_{i \bmod k=m} a^i \binom ni \\ &= \sum_{i=0}^n [k|i-m] a^i \binom ni \\ &= \sum_{i=0}^n \frac 1k \sum_{j=0}^{k-1} \omega_k^{j(i-m)} a^i \binom ni \\ &= \frac 1k \sum_{j=0}^{k-1} \omega^{-mj}_k \sum_{i=0}^n \binom ni (\omega^{j}_k a)^i 1^{n-i} \\ &= \frac 1k \sum_{i=0}^{k-1} \omega^{-mi}_k \left(\omega^i_k a + 1\right)^n \end{aligned}

考虑后面的 \displaystyle{\left(\omega^i_k a + 1\right)^n} 对于固定的 i 是相同的，可以与先处理出 i \in [0, k) 的值，设为 c(i)。

前面的部分有个暴力的做法就是多项式多点求值出多项式 \displaystyle{\frac 1k \sum_{i=0}^{k-1} x^i c(i)} 在 \omega_k^0, \omega_k^{-1}, \omega_k^{-2} ... \omega_k^{-k+1} 的值，复杂度 O(k \log^2 k)，然而貌似被针对了过不去 ...

考虑一个优秀一点的做法，如何处理 \omega^{-mj}？毛爷爷论文中有个做法是把 ij 拆成 \frac {(i+j)^2} 2 - \frac {i^2} 2 - \frac {j^2} 2 ，然而此题中可能存在单位根没有二次剩余的情况。考虑把 ij 拆成 \binom {i+j} 2 - \binom i2 - \binom j2 ，那么原式可以化为

\begin{aligned} ans &= \frac 1k \sum_{i=0}^{k-1} \omega^{-mi}_k c(i) \\ &= \frac 1k \sum_{i=0}^{k-1} \omega^{\binom {i-m} 2 - \binom i2 - \binom {-m}2} _k c(i) \\ &= \frac {\omega^{- \binom {-m}2}} k \sum_{i=0}^{k-1} \omega^{\binom {i-m} 2}_k \left( \omega^{- \binom i2}_k c(i)\right) \\ \end{aligned}

显然是一个卷积的形式，那么卷积下即可，复杂度 O(k \log k)。

考虑 n \le 3 的情况，原来的转移会变成矩阵，感兴趣的读者可以先做下 BZOJ3328 PYXFIB ，与 n = 1 是本质相同的，并且可以发现 c(i) 仍然是一个常数，同理处理下再卷积即可。

READ MORE

考虑最暴力的做法，列出 n 个生成函数，FWT 到一起，复杂度 \mathcal O(n \times 2^k \times k) ，显然不能通过。

考虑三元组 (a_i, b_i, c_i) 对 ans_k 的贡献，等价于三元组 (0, a_i \operatorname{xor} b_i, a_i \operatorname{xor} c_i) 对 ans_{k \operatorname{xor} a_i} 的贡献。考虑这样将题意转化后，生成函数只有 0、a_i \operatorname{xor} b_i、a_i \operatorname{xor} c_i 下标上有值（分别为 a, b, c）。那么经过一次 FWT 后，只有四个位置上有值，且值分别为 a+b+c, a+b-c, a-b+c, a-b-c。

考虑将 n 个生成函数加起来做 FWT ，假设 a+b+c, a+b-c, a-b+c, a-b-c 分别在其中出现了 x, y, z, w 次，那么这个位置在正常做法情况下的值应该为 (a+b+c)^x \times (a+b-c)^y \times (a-b+c)^z \times (a-b-c)^w ，也就是说我们需要解出这个 x, y, z, w 的值。

首先显然的 x + y + z + w = p，p 是这位上当前的值。需要注意的是，这个 a, b, c 并不一定需要是题目中给出的，所以我们可以分别取 (0, 1, 0) 和 (0, 0, 1) ，列出两个方程，此时我们若再通过改变 (a, b, c) 来列方程，则可以通过两个已有的来表示，本质相同的，需要考虑别的方式得到新的方程。

考虑构造一个新的多项式，对于每个 k = b_i \operatorname{xor} c_i 让 k \text{+=} 1 ，这样的话可以得到一个新的方程 x + y + z + w = q ，q 是这位上当前的值。

这样的话我们就得到了四个本质不同方程，可以解除上面的 x, y, z, w ，得出正常 FWT 后应该得到的点值，再将其 IFWT 一次即可得到答案。

READ MORE

  1. 1
  2. 2
  3. 3
  4. 4
  5. ...
  6. 12