当我跨过沉沦的一切
向着永恒开战的时候
你是我的军旗

memset0 发布的文章

官方题解是什么神仙东西看啊看不懂的。

Link

考虑我们维护一个分数类 (x, y) 表示 \frac x y 。假设 f(a_1, a_2, ..., a_n) = \frac x y 那么 f(a_0, a_1, a_2, ..., a_n) = \frac {a_0 x + y} {x} 。可以考虑用矩阵来维护转移。

定义将 (x, y)(a x + y, x) 的转移为

\left[\begin{matrix} a & 1 \\ 1 & 0 \\ \end{matrix}\right] \left[\begin{matrix} x \\ y \\ \end{matrix}\right] = \left[\begin{matrix} ax + y \\ x \end{matrix}\right]

反之,从 (ax + y, x)(x, y) 的转移为

\left[\begin{matrix} 0 & 1 \\ 1 & -a \\ \end{matrix}\right] \left[\begin{matrix} ax + y \\ x \\ \end{matrix}\right] = \left[\begin{matrix} x \\ y \\ \end{matrix}\right]

那么

\begin{aligned} Ans_{l, r} &= \left[\begin{matrix} a_l & 1 \\ 1 & 0 \\ \end{matrix}\right] \left[\begin{matrix} a_{l + 1} & 1 \\ 1 & 0 \\ \end{matrix}\right] \cdots \left[\begin{matrix} a_r & 1 \\ 1 & 0 \\ \end{matrix}\right] \left[\begin{matrix} 1 \\ 0 \end{matrix}\right] \\ &= \left[\begin{matrix} 0 & 1 \\ 1 & -a_{l - 1} \\ \end{matrix}\right] \left[\begin{matrix} 0 & 1 \\ 1 & -a_{l - 2} \\ \end{matrix}\right] \cdots \left[\begin{matrix} 0 & 1 \\ 1 & -a_1 \\ \end{matrix}\right] \left[\begin{matrix} a_1 & 1 \\ 1 & 0 \\ \end{matrix}\right] \left[\begin{matrix} a_2 & 1 \\ 1 & 0 \\ \end{matrix}\right] \cdots \left[\begin{matrix} a_r & 1 \\ 1 & 0 \\ \end{matrix}\right] \left[\begin{matrix} 1 \\ 0 \end{matrix}\right] \end{aligned}

可以分别处理出前缀和

\begin{aligned} F_n &= \left[\begin{matrix} a_1 & 1 \\ 1 & 0 \\ \end{matrix}\right] \left[\begin{matrix} a_2 & 1 \\ 1 & 0 \\ \end{matrix}\right] \cdots \left[\begin{matrix} a_n & 1 \\ 1 & 0 \\ \end{matrix}\right] \\ G_n &= \left[\begin{matrix} 0 & 1 \\ 1 & -a_{n} \\ \end{matrix}\right] \left[\begin{matrix} 0 & 1 \\ 1 & -a_{n - 1} \\ \end{matrix}\right] \cdots \left[\begin{matrix} 0 & 1 \\ 1 & -a_1 \\ \end{matrix}\right] \end{aligned}

READ MORE

对于给定的 n+1 个点的坐标可以列出 n+1 个方程

\begin{cases} \left( a_{1, 1} - x_1 \right)^2 + \left( a_{1, 2} - x_2 \right)^2 + ... + \left( a_{1, n} - x_n \right)^2 = r^2 \\ \left( a_{2, 1} - x_1 \right)^2 + \left( a_{2, 2} - x_2 \right)^2 + ... + \left( a_{2, n} - x_n \right)^2 = r^2 \\ ... \\ \left( a_{n+1, 1} - x_1 \right)^2 + \left( a_{n+1, 2} - x_2 \right)^2 + ... + \left( a_{n+1, n} - x_n \right)^2 = r^2 \\ \end{cases}

考虑展开以后的 r^2x_{1...n}^2 比较难以处理。让 [2, n + 1] 方程与第一个方程做差,得到 n 个线性方程

\begin{cases} a_{2, 1}^2 - a_{1, 1}^2 - 2 x_1 (a_{2, 1} - a_{1, 1}) + a_{2, 2}^2 - a_{1, 2}^2 - 2 x_1 (a_{2, 2} - a_{1, 2}) + ... + a_{2, n}^2 - a_{1, n}^2 - 2 x_1 (a_{2, n} - a_{1, n}) = 0 \\ a_{3, 1}^2 - a_{1, 1}^2 - 2 x_1 (a_{3, 1} - a_{1, 1}) + a_{3, 2}^2 - a_{1, 2}^2 - 2 x_1 (a_{3, 2} - a_{1, 2}) + ... + a_{3, n}^2 - a_{1, n}^2 - 2 x_1 (a_{3, n} - a_{1, n}) = 0 \\ ...\\ a_{n+1, 1}^2 - a_{1, 1}^2 - 2 x_1 (a_{n+1, 1} - a_{1, 1}) + a_{n+1, 2}^2 - a_{1, 2}^2 - 2 x_1 (a_{n+1, 2} - a_{1, 2}) + ... + a_{n+1, n}^2 - a_{1, n}^2 - 2 x_1 (a_{n+1, n} - a_{1, n}) = 0 \\ \end{cases}

高斯消元即可求得

同时考虑点权和边权比较困难,如果可以把边权并到点权里,那么就可以直接贪心了。

注意到对于一条边的边权对答案的贡献

  • 如果两边都是黑点,对答案的贡献为 1 ,可以看做两个黑点分别为答案贡献了 \frac 1 2
  • 如果两边都是白点,对答案的贡献为 -1 ,可以看做两个白点分别为答案贡献了 - \frac 1 2
  • 如果一边是白点一边是黑点,贡献为 0 ,可以看做黑点为答案贡献了 \frac 1 2 的边权,白点为答案贡献了 - \frac 1 2 的贡献

这样话设置每个点的排序关键字为点权加上 \frac 1 2 的相邻边权和,按从大到小排序后奇数位为黑点,偶数位为白点即可。

READ MORE

\clubsuit 是 OI 国马拉松协会的会长。有一天,他打算举办全国青少年马拉松奥林匹克联赛(National Olympiad in Marathon in Provinces, NOMP),于是准备在 OI 国中修建一条赛道。

OI 国有 n (n \leq 5 \times 10^4) 个城市,一共有 n - 1 条道路将它们连通。也就是说,OI 国的结构是一棵树。

\clubsuit 会选择一个城市作为起点,再选择一个城市作为终点,这样赛道的长度就等于起点到终点路径上的边数。由于 OI 国的群众非常懒,所以赛道长为 0 也是允许的。

由于一些特殊原因,赛道的终点只能是一些特定的城市,而赛道的起点可以是任意一个城市。

现在小 \clubsuit 想知道:对于每个城市,如果选择它作为起点,那么赛道的长度有几种可能的取值?

READ MORE

给定 n 和长度为 n 的数组 \{a_i \} _{i=1}^n ,求满足 \forall i \in [1, n], c_i | b_i, b_i | a_i 并且 \prod_{i=1}^n c_i^2 \leq \prod_{i=1}^n b_i\{b_i\}_{i=1}^n\{c_i\}_{i=1}^n 的方案数。

n \leq 100,\ a_i \leq 10^9

READ MORE

可以发现每条边出现的概率都是相同的,那么

ans = \frac{2 n^{n-3}}{n^{n-2}} \sum_{i=1}^{n} \sum_{j=i+1}^{n} (i+j)^k = \frac 2 n \sum_{i=1}^n \sum_{j=i+1}^n (i+j)^k

只需要求后面的值,假设 f(n, k) = \sum_{i=1}^n i^k

\begin{aligned} \sum_{i=1}^n \sum_{j=i+1}^n (i+j)^k &= \frac 1 2 \left( \sum_{i=1}^n \sum_{j=1}^n (i+j)^k - \sum_{i=1}^n (i+i)^k \right) \\ &= 2^{-1} \sum_{i=1}^n \sum_{j=1}^n (i+j)^k - 2^{k-1} \sum_{i=1}^n i^k \\ &= 2^{-1} \sum_{i=1}^n \sum_{j=1}^n (i+j)^k - 2^{k-1} f(n, k) \end{aligned}

只需要求中间的那个双重和式,后面的可以插值

\begin{aligned} \sum_{i=1}^n \sum_{j=1}^n (i+j)^k &= \sum_{d=1}^{2n} d^k \sum_{i=1}^n \sum_{j=1}^n [i+j=d] \\ &= \sum_{d=1}^n d^k (d-1) + \sum_{d=n}^{2n} d^k \left(2n-(d-1)\right) \\ &= \sum_{d=1}^{n-1} d^{k+1} + \sum_{d=n}^{2n} 2n d^k - \sum_{d=n-1}^{2n-1} d^{k+1} \\ &= f(n-1, k+1) + 2n \left( f(2n, k) - f(n-1, k) \right) - \left( f(2n-1, k+1) - f(n-2, k+1)\right)\\ \end{aligned}

可以处理出 f(n, k), f(2n, k), f(n, k+1), f(2n, k+1) 并快速转移。复杂度为拉格朗日插值的复杂度。

发现主要瓶颈在于 1. 求快速幂 2. 求逆元 。前者是一个完全积性函数,可以使用线性筛求得;后者我们可以先线性求逆元,然后分别做一趟前缀 / 后缀和即可。

傻逼题,CF 的数据是假的,不开 std::multiset 都可以过。

发现我们直接缩成一棵广义圆方树然后进行维护。修改点权的时候如果我们暴力修改圆点周围的方点显然可能挂掉,但是如果我们的方点只存圆方树上孩子的信息,那么就只用更新 O(1) 次了,这样的话在求 u \rightarrow v 的路径的时候判断一下 LCA 是不是方点即可。时间复杂度 O(n \log^2 n)

READ MORE