怎样提高智商

from vfleaking

算法一

有一种算法叫做手算。只要你脑力足够，算出 $n = 2, 3$ 什么的大概没有问题。可以获得 20 分。

算法二

有一种算法叫做爆搜。我们裸暴力搜索 $h_i, a_i, b_i, c_i, d_i$ 再裸暴力求方案数，只要你不是写得太糟糕，考试三个小时跑出 $n = 2, 3, 4$ 还是妥妥的。对于 $n = 5, 6$ 的话留给人类智慧达人、搜索剪枝达人、随机化乱搞达人、模拟退火达人。

这题我不会做，但是我能A

其实你只要把小范围的答案搜出来会发现是 $4, 12, 36, 108$ （假设你没搜出 $5, 6$），这时就要胆子大一点，说不定答案最多就是 $4 \times 3^{n - 1}$ 种！

然后打出方案之后我们就更放心了。

• 1. 编号小于 $1$ 的题目中你一共选了几个 A？

  • A. $0$ 个
  • B. $0$ 个
  • C. $0$ 个
  • D. $0$ 个

• 2. 编号小于 $2$ 的题目中你一共选了几个 A？

  • A. $0$ 个
  • B. $0$ 个
  • C. $0$ 个
  • D. $0$ 个

• 3. 编号小于 $3$ 的题目中你一共选了几个 A？

  • A. $0$ 个
  • B. $0$ 个
  • C. $0$ 个
  • D. $0$ 个

这样看起来就感觉是最多的，掐之一算确实是 $4 \times 3^{n - 1}$。恭喜你，你猜的都是对的！于是就这么愉快地AC啦。

可不可以靠谱一点啊

我们考虑一张试卷，考虑每次填答案，如果每次我都有不超过 $3$ 个选项可以选，那么总答案数肯定不超过 $3^n$。

如果要比 $4 \times 3^{n - 1}$ 大，肯定存在一道题 $i$，使得存在一种 $1$ 到 $i - 1$ 题的正确答案当填到第 $i$ 题时接下来 $4$ 个选项都可以选。我们称这张试卷上的这种题叫 sb 题。

假设 $1$ 到 $i - 1$ 题共有 $d$ 种答案，如果第 $i$ 道题不是 sb 题，那么前 $i$ 题的正确答案不会超过 $3d$。如果是一道 sb 题，那么我们看第 $i + 1$ 题。不妨设这道题是问 C 的数量。现在看这道题的选项 A，假设要求 C 有 $a_{i + 1}$ 个，并假设刚才的 $1$ 到 $i - 1$ 题的 $d$ 种答案中有 $p$ 个答案有 $a_{i + 1}$ 个 C，有 $q$ 个答案有 $a_{i + 1} - 1$ 个 C。在做了第 $i$ 道题之后，我们有不超过 $4d$ 个答案，这些答案中有不超过 $3p + q$ 个答案有 $a_{i + 1}$ 个 C。那么现在满足条件第 $i + 1$ 题的 A 选项的就只有不超过 $3p + q$ 个答案。由于 $3p + q = 2p + (p + q) \leq 2p + d \leq 3d$，所以对于第 $i + 1$ 道题，对于每个选项，能选它的都只有不超过 $3d$ 个答案。考虑选 A 的那不超过 $3d$ 个答案，继续下去看第 $i + 2$ 题时，我们也可以通过相同的证明过程证明对于每个选项，能选的都只有不超过 $9d$ 个。如此下来我们就可以证明假设这道 sb 题后面有 $l$ 题，那么总答案数不会超过 $4 \times 3^l$ 个。由于在前 $i - 1$ 道题中没有 sb 题，所以 $d \leq 3^{i - 1}$。

于是我们就证明了，如果没有 sb 题，答案数不超过 $3^n$，如果有 sb 题，答案数不超过 $4 \times 3^{n - 1}$。而且我们又找出了一个答案数恰好为 $4 \times 3^{n - 1}$ 的，所以最多的答案数为 $4 \times 3^{n - 1}$。

什么你不知道为什么全是 A 全是 $0$ 的话有 $4 \times 3^{n - 1}$ 个？显然前 $n - 1$ 道题中 A 必须一个都不选不然最后一道题就没得选的，当做最后一道题的时候 ABCD 瞎选一通，这样总共就是 $4 \times 3^{n - 1}$ 个。

怎样更有力气

from jiry_2

算法一

我们可以把所有边连出来然后暴力跑最小生成树，时间复杂度$O(n^3)$（为了方便我把$n,m,p$都看成$n$），期望得分10分。

算法二

引理一：对于一张已有的边长度都小于等于$w$无向图，我们在一个点集中连上若干条长度为$w$的边，如果满足只看新加上的这些边以及这个点集（把其他的点和边都删去），图仍然联通，那么所有这样的方案对于求最小生成树这个问题来说是等价的。

简要的证明如下：

首先对于求最小生成树这个问题来说，如果我们从小到大插入边，那么已经在一个联通块中所有的点是等价的。如果我们把这个点集里的所有点连成完全图时合并了$k$个联通块，那么我们在考虑其他的方案的时候，把原有的联通块缩成点，则因为新加的边使点集联通，所以一定存在一个边集使得这$k$个联通块缩点后的点联通（连通无向图一定存在最小生成树）。

所以我们只需要对每一个询问连$O(n)$条边就好了。显然当$p=0$的时候由引理一我们连的边可以都是树边，而每一条树边只有最小的那次覆盖是计入答案的，所以就相当于求解链取min以及单条边查询的问题。这个问题离线用并查集可以做到$O(n \alpha_n)$，期望得分40分。

算法三

因为树形状为链时的算法和树没有太大的算法没有具体的区别（为链的情况专门为一些奇葩算法比如要维护区间啊啥的以及细节写残的标算准备），所以接下来开始介绍标算。

由引理一，对于每一个修建操作，求出联通块之后，我们只需要考虑这个操作的点数条边就好了。但是我们只知道实际连边的补图，直接求联通块的复杂度是$O(n^2)$的。

我们可以选取度数最小的点，没有和这个点连边的所有点一定是和这个点在一个联通块中，剩下的点暴力连边DFS就好了。

假设当前操作的补图有$a$个点$b$条边，那么最小度数的点的度数一定小于$\frac{2b}{a}$，又$\sum b=p$，所以可以得到这个方法的总复杂度是$O(p)$的。

如果一次修建操作中，存在一个点它没有删过一条相连的边，那么这一次修建操作的所有点一定联通，这时我们只需要和算法二一样处理就好了。

那么我们要单独处理的修建操作总点数是$O(p)$的。这种操作的点被分成了若干个联通块，我们把这些联通块分开来考虑，对于一个联通块，在树上对应了一些链，显然每一条链都是一个联通块。所以我们可以在第$i$条链和第$i+1$条链之间只保留一条边，而区间内部的边就和算法二一样处理即可。

这样在一番预处理之后，我们得到了很多条单独联通的链和很多条单独的边，而链可以通过算法二的方案处理得只剩下$O(n)$条边，单独的边数也一定是$O(p)$的，所以最后再跑一遍最小生成树就好了。时间复杂度$O(n \log n)$，期望得分100分。

其它算法

咳咳大家好我是 vfleaking，我来说下我的算法。由于连通块在树上可能不是连续的，所以我们用两个并查集维护这个图，第一个并查集会把在一个连通块的点缩起来，而第二个并查集，如果结点 $v$ 和结点 $v$ 的父亲在一个连通块，那么他们就会被缩起来。第二个并查集里的一个连通块肯定是树上连续的一坨，于是就可以很方便地操作。

看起来我们要同时操纵两个并查集？其实第二个并查集没必要特别维护，只要在每次 find_father 找到达到顶端时，顺便检查下跟自己的父亲是不是在一个连通块，是的话就自动缩起来再继续 find_father。

我们还是把 $m$ 天按边权排序，然后每次我们暴力在树上爬找到 $v_i$ 到 $u_i$ 这条路径对应的第二个并查集里的那些块块，并找到对应的连通块。然后我们只要暴力 for 每条连接不同连通块的边，判断是否被禁止，如果没禁止就把连通块缩起来（这样的操作至多只有连通块个数减一次），如果被禁止了就不管（这样的操作至多只有被禁止的边数次）。这里缩起来只用管管第一个并查集，对于第二个并查集是自动维护的。于是就可以嘴巴AC了！

可是怎样才能每次快准狠找一个连接两个不同连通块的边？这个就乱搞吧。我的方法是把连通块依次加入，每次考虑新加进来的和之前的已加入的连通块之间的边，暴力扫扫，最后把被合并的连通块清理掉（因为已经和那个新的连通块是一体的了）。

如果你跟我想得一样，那么是链的情况就有点良心，因为我们可以不用第二个并查集，而是用一个 STL 的 set 或者 map 维护是同一个连通块的区间。当然，还是自动维护。

怎样跑得更快

from taorunz

算法一

对于第一个数据，$n=3$，我们直接用手推出公式就可以啦！

期望得分：5分

算法二

对于20%的数据$n \leq 100, q \leq 100$，我们可以对每一个询问进行高斯消元。时间复杂度$O(n^3)$

期望得分：20分（如果你卡常数卡的好，可以通过$n=1000,q=1$的三个数据，得到35分）

算法三

对于40%的数据$n \leq 100, q \leq 1000$，我们可以先使用高斯消元求出逆矩阵，之后计算 $x$ 只要用逆矩阵乘上 $b$ 即可。时间复杂度$O(qn^2)$

期望得分：40分（如果你卡常数卡的好，可以通过$n=1000$的五个数据（除了12号），期望得分：65分。

算法四

到此为止，我们的解法都没有用到$\gcd^c(i,j)\lcm^d(i,j)$这个条件。我们如何使用呢？

对于点2，12，17，有$c=d$,这个时候，方程化为 \begin{equation} \sum_{j=1}^n i^c j^c x_j = b_i \end{equation}

这个就等价于： \begin{equation} \sum_{j=1}^n j^c x_j = b_i / i^c \end{equation}

我们发现，方程右端与 $i$ 无关！这样，我们比较$b_i/i^c$的值，如果全部相同则输出一组解（比如$b_1,0,\dots,0$），否则输出-1

这样可以得到15分。加上算法四可以得到50分（卡常数75分）

算法五

对于点5，15，16，有 $c=1，d=0$。方程组就是

\begin{equation} \sum_{j=1}^n \gcd(i,j) x_j = b_i \end{equation}

我们把这个矩阵$a_{ij}=\gcd(i,j)$表示出来，发现它可以表示为

\begin{equation} [[j \mid i]]_{n\times n} \cdot \mathrm{diag}(\varphi(1)...\varphi(n)) \cdot [[i \mid j]]_{n\times n} \end{equation}

我们还可以发现：$[[i \mid j]]$的逆矩阵就是$[\mu(i/j) [i \mid j]]$这样，我们的逆矩阵就变成求：

\begin{equation} \sum_k [i \mid k][j \mid k] \mu(k/i) \mu(k/j) \varphi^{-1}(k) \end{equation}

对于$c, d$任意的情况，我们将$\varphi$换成jordan函数 $J_{k}$ 也可以同样计算。

注意到$k$是$\lcm(i,j)$的倍数，我们暴力求解这个逆矩阵，在对每个询问乘上$b$，这样就可以通过$n=1000$的数据。期望得分 70 分。

我们只要把乘上 $b$ 的式子写一下就可以发现是很好 $O(n \log n)$ 进行计算的。对于行列式为 $0$ 的情况可能出现无解会多解，唯一的可能是 jordan 函数为 $0$。我们可以把那些需要除以 $0$ 的项随便赋值，跑出来后再回代检验解的正确性就行了。期望得分 100 分。

好懂的算法

咳咳大家好我是 vfleaking，我来说下好懂的。

首先学过小学奥数的我们知道：$\lcm(i, j) = \frac{ij}{\gcd(i. j)}$。所以这题其实是：

\begin{equation} \sum_{j=1}^n \gcd(i,j)^{c - d} \cdot i^d \cdot j^d \cdot x_j = b_i \end{equation}

但是其实这种题都可做：

\begin{equation} \sum_{j=1}^n f(\gcd(i,j)) \cdot g(i) \cdot h(j) \cdot x_j = b_i \end{equation}

可能很多人的注意力都在“这玩意儿怎么解啊”，其实只要换个姿势问问自己 “要是有人告诉了我 $x$，我应该怎么验证它是对的呢？” 这题就可做了。

其实关键的坑人的地方在于 $f(\gcd(i,j))$。假设我有一个函数 $f_r(n)$，满足 $f(n) = \sum_{d \mid n}{f_r(d)}$，其中 $d \mid n$ 表示 $d$ 是 $n$ 的约数。这个式子的意思是，$f(n)$ 等于所有 $n$ 的约数带进 $f_r$ 后的和。知道 $f$ 后 $f_r$ 是很好搞的，因为 $f_r(n) = f(n) - \sum_{d \mid n \text{且} d \neq n}{f_r(d)}$，所以就能递推了。妈呀，怎么枚举约数啊？其实只要这样搞就行了：

for (int i = 1; i <= n; i++)
    f_r[i] = f[i];
for (int i = 1; i <= n; i++)
    for (int j = i + i; j <= n; j += i)
        f_r[j] -= f_r[i];

看起来是 $O(n^2)$ 的？好吧如果你不知道这是 $O(n \log n)$ 的话就是个悲伤的故事。由于 $\sum_{i = 1}^{n}{\frac{1}{i}} = O(\log n)$，所以 $\sum_{i = 1}^{n}{\frac{n}{i}} = O(n \log n)$。

为什么要这样？因为我们知道如果 $d \mid \gcd(i, j)$ 那么肯定有 $d \mid i$ 且 $d \mid j$，反之亦然。这样就把讨厌的 $\gcd$ 给去掉了。

所以我们可以写出这样的等式：

\begin{equation} \sum_{j=1}^n \sum_{d}[d \mid i][d \mid j] \cdot f_r(d) \cdot g(i) \cdot h(j) \cdot x_j = b_i \end{equation} 这里有个符号： $[P]$ 表示表达式 $P$ 为真时值为 $1$ 否则为 $0$。比如 $[d \mid i]$ 的值在 $d \mid i$ 时为 $1$ 否则为 $0$。

接下来怎么办？好像并没有简化问题。我们把两个求和符号反过来，得到：

\begin{equation} \sum_{d} \sum_{j=1}^n [d \mid i][d \mid j] \cdot f_r(d) \cdot g(i) \cdot h(j) \cdot x_j = b_i \end{equation}

然后我们移一下项：

\begin{equation} \sum_{d \mid i} f_r(d) \sum_{j=1}^{n} [d \mid j] \cdot h(j) \cdot x_j = b_i / g(i) \end{equation}

仔细观察，发现 $\sum_{j=1}^{n} [d \mid j] \cdot h(j) \cdot x_j$ 的意思是把所有 $j$ 是 $d$ 的倍数的 $h(j) \cdot x_j$ 加起来。反正这个只跟 $d$ 的值有关，我们记为 $z_d$。于是我们得到：

\begin{equation} \sum_{d \mid i} f_r(d) z_d = b_i / g(i) \end{equation}

这个式子的意思是，对于每个 $i$，把所有 $d$ 是 $i$ 的约数的 $f_r(d) z_d$ 加起来，得到结果 $b_i / g(i)$。现在我们知道右边，想求左边。似曾相识，对不对？

for (int i = 1; i <= n; i++)
    f_z[i] = b[i] / g(i);
for (int i = 1; i <= n; i++)
    for (int j = i + i; j <= n; j += i)
        f_z[j] -= f_z[i];

这样得到的 $f_z[d]$ 就是 $f_r(d) z_d$。想得到 $z_d$？由于 $f_r(d)$ 已经求出，所以 $z_d = f_z[d] / f_r(d)$。

但是 $z_d$ 并不是最终答案。回忆 $z_d$ 的表达式：

\begin{equation} z_d = \sum_{j=1}^{n} [d \mid j] \cdot h(j) \cdot x_j \end{equation}

现在知道左边，想求右边，怎么办？是不是还是似曾相识呢！由于我们知道 $h(d) \cdot x_d = z_d - \sum_{j=1}^{n} [j > d][d \mid j] \cdot h(j) \cdot x_j$，所以：

for (int i = 1; i <= n; i++)
    hx[i] = z[d];
for (int i = n; i >= 1; i--)
    for (int j = i + i; j <= n; j += i)
        hx[i] -= hx[j];

嗯，现在我们知道了 $h(j) x_j$，那么 $x_j$ 就好求了。

由于中间过程涉及了除法，所以就会带来无解和多解的情况。对于本题 $g(i)$ 和 $h(j)$ 肯定都不是 $p$ 的倍数，所以都有逆元。而 $f_r(d)$ 可能没有逆元。这种情况假如 $f_z[d] \neq 0$ 那么显然无解，如果 $f_z[d] = 0$ 就有多组解，我们把 $z_d$ 随便附个值比如让 $z_d = 0$ 就好了。

罗嗦了半天其实跟算法五本质是一样的。这题其实就是把 $b$ 除以 $g(i)$ 然后莫比乌斯反演，然后除以 $f$ 的莫比乌斯反演，再进行莫比乌斯反演，再除以 $h(j)$，三个莫比乌斯反演掷地有声。