几度风雨几度春秋 风霜雪雨博激流
历尽苦难痴心不改 少年壮志不言愁

分类 题解 下的文章

把询问拆分后直接莫队。

考虑

\begin{aligned} \sum_{i=0}^{\infty} get(l_1, r_1, x) \times get(l_2, r_2, x) = &\sum_{i=0}^{\infty} get(0, r_1, x) \times get(0, r_2, x)\\ - &\sum_{i=0}^{\infty} get(0, l_1-1, x) \times get(0, r_2, x)\\ - &\sum_{i=0}^{\infty} get(0, r_1, x) \times get(0, l_2-1, x) \\ + &\sum_{i=0}^{\infty} get(0, l_1-1, x) \times get(0, l_2-1, x) \end{aligned}

一个比较通俗的理解是 (A - C) (B - D) = AB - BC - AD + CD

READ MORE

给定一个网格图,边有边权,给定 M 个查询,求两点最短路。

考虑离线所有询问,然后分治,假设当前分治一条横穿中心的线,枚举每个线上节点更新当前所有询问的答案。

  • 若某查询的两点在此线两侧,则最短路一定能在此次被更新

  • 若某查询的两点在此线同侧,则最短路可能被当前更新,可以递归下去做。

可以证明每次选当前分治矩形的最长边,时间复杂度为 O(n \sqrt n \log n)

READ MORE

题目要求恰好等于 M 的方案数,我们只需要求出小于等于 M 的和小于等于 M-1 的,相减即可。

考虑 Purfer 序列,他的长度为 N - 2,按照题目要求,每个数只能出现 0 ~ M - 1 次,考虑组合生成函数 f(x) = \sum\limits_{i=0}^{m-1} \frac {x^i} {i!} ,那么答案即 (N-2)![x^{N-2}]f^N(x)

READ MORE

考虑每一个标记一定对模 x 同余的所有数进行修改。

对于 x \le \sqrt n 的标记,我们维护出 x 相同的操作的 y 值前缀和,这样 x 相同的标记对当前查询的贡献就可以分为整块 + 前缀和 + 后缀和。

对于 x > \sqrt n 的标记,我们对原序列分块,则每一个修改一定在不同的块中,我们暴力修改 + 暴力统计每个块的和即可。

总时间复杂度 O(n \sqrt n) ,卡卡常可以通过此题。

READ MORE

f_i 表示 i 个时的高度之和, g_i 表示 i 个时的方案数,显然:

\begin{aligned} g_n &= \sum\limits_{i=1}^n {n \choose i} g_{n-i} \\ f_n &= g_n + \sum\limits_{i=1}^n {n \choose i} f_{n-i} \\ ans_n &= f_n \times g_n^{-1} \end{aligned}

其实到这里可以直接分治 NTT ,不过我们考虑多项式求逆的做法。 首先把 {n \choose i} 拆开,然后设 F_n = f_n / n!G_n = g_n / n!H_n = 1 / n!

\begin{aligned} G &= (2 - H)^{-1} \\ F &= (G - 1) (2 - H)^{-1} \\ ans_n &= F_n G_n^{-1} \end{aligned}

(推导时需要注意常数项系数,f_0 = 0,g_0 = h_0 = 1。)

READ MORE

数据范围容易想到利用矩阵进行计算。

考虑 f(k) = (A, B) ,其中 A 表示恰好等于 k 的路径条数, B 表示小于等于 k 的路径条数。则可以这样转移: (A, B) \times (C, D) = (A \times C, B + A \times D)

需要注意的是,对长度为 L 的路径对答案的贡献可以表示为一个二次多项式(即 f(L) = L ^ 2),转移时不能直接计算,而需要记录一次项和常数项系数。注意多项式乘法时需要乘上组合数。

READ MORE

P(S) 为钦点 S 中所有元素都在 1 之后挂掉的概率,显然:

P(s) = \frac{a_1}{sum(S) + a_1}

于是我们可以发现最后答案为:

ans = \sum\limits_{S \in [2, n]} P(S) (-1)^{|S|}

于是分治 + NTT 即可。

至此除斗地主外的所有 PKUWC 2018 题目已经订正完毕,祝也去参加 PKUWC 的读者和自己 RP = +\infty qwq!

READ MORE