水题记录1.2

41/50

水题记录1.2

T1.BZOJ1801[AHOI2009]中国象棋

给你一个\(n \times m\)的矩阵, 你可以随便放一些炮, 保证每行每列的炮的个数都小于等于二求方案数

考虑一下 \(dp\) , 设\(f_{i,j,k}\) 表示考虑了前 \(i\) 行有 \(j\) 列放了一个 \(k\) 列放了两个的方案数

然后我们枚举一下这一行放的炮的个数, 然后讨论一下放在哪

转移显然 \[ f_{i,j,k} \to \begin{cases} f_{i + 1,j,k} \\ f_{i + 1, j + 1, k} \ \ \ \ \ \ if\ m - j - k \ge 1\\ f_{i + 1, j - 1, k + 1} \ \ if \ \ j \ge 1 \\ f_{i + 1, j, k + 1} \ \ \ \ \ if \ \ m - j - k \ge 1 \ \ and \ \ j \ge 1 \\ f_{i + 1, j + 2, k} \ \ \ \ \ if\ \ m - j - k \ge 2 \\ f_{i + 1, j - 2, k + 2} \ \ if \ \ j \ge 2\end{cases} \]

T2.LUOGUP4948 数列求和

\[ S_n(k) = \sum _ {i = 1} ^ {n} i^k \cdot a^i \]

\(S_n(k) \ \ mod (10^9 + 7)\)

\(n \le 10^{18}, k \le 2000, a \le 10^9\)

考虑化一下式子 \[ a \cdot S_n(k) = 0^k \cdot a^1 + 1^k \cdot a^2 + \cdots + (n - 1)^k \cdot a^n + n^k \cdot a^{n + 1} \]

\[ S_n(k) = 1^k \cdot a^1 + 2^k \cdot a^2 + \cdots + n^k \cdot a^n \]

两式相减得 \[ (a - 1) \cdot S_n(k) = n^k \cdot a^{n + 1} + \sum _ {i = 1} ^ n a^i \cdot ((i - 1)^k - i ^ k) \] 二项式定理展开一下 \[ (a - 1) \cdot S_n(k) = n^k \cdot a^{n + 1} + \sum _ {i = 1} ^ n a^i \cdot (\sum _ {j = 0} ^ {k} \binom{k}{j}i^j(-1)^{k - j} - i^k) \]

\[ (a - 1) \cdot S_n(k) = n^k \cdot a^{n + 1} + \sum _ {i = 1} ^ n a^i \cdot \sum _ {j = 0} ^ {k - 1} \binom{k}{j}i^j(-1)^{k - j} \]

改变一下求和顺序 \[ (a - 1) \cdot S_n(k) = n^k \cdot a^{n + 1} + \sum _ {j = 0} ^ {k - 1} \binom{k}{j}(-1)^{k - j}\sum _ {i = 1} ^ {n}a^i \cdot i ^ j \] 发现 \(\sum_{i = 1}^n a^i \cdot i^j\) 其实就是 \(S_n(j)\)

所以 \[ S_n(k) = \frac{n^k \cdot a^{n + 1} + \sum _ {j = 0} ^ {k - 1} \binom{k}{j}(-1)^{k - j} \cdot S_n(j)}{a - 1} \] \(O(k ^ 2)\) 递推一下就好了

好了终于推完了, 但是我们又发现了一个问题当 \(a = 1\)时这个式子是不成立的

所以我们再分类讨论一波

\(a = 1\)\[ S_n(k) = \sum_{i = 1} ^ {k} i ^ k \] 发现是个自然数幂, 对我们可以直接伯努利数啊

假的其实并不会, 那就继续推一下 \[ S_n(k) = \sum _ {i = 1} ^ n (i + 1) ^ k - (n + 1) ^ k +1 \]

\[ S_n(k) = \sum _ {i = 1} ^ n \sum _ {j = 0} ^ k \binom{k}{j} \cdot i^j - (n + 1) ^ k + 1 \]

改变求和顺序 \[ S_n(k) = \sum _ {j = 0} ^ k\binom{k}{j} \cdot\sum _ {i = 1} ^ n i^j - (n + 1) ^ k + 1 \]

\[ S_n(k) = \sum _ {j = 0} ^ k\binom{k}{j} \cdot S_n(j) - (n + 1) ^ k + 1 \]

\[ \sum _ {j = 0} ^ {k - 1} \binom{k}{j} \cdot S_n(j) = (n + 1) ^ k - 1 \]

\[ \sum _ {j = 0} ^ {k - 2} \binom{k}{j} \cdot S_n(j) + S_n(k - 1) \cdot \binom{k}{k - 1} = (n + 1) ^ k - 1 \]

\[ k \cdot S_n(k - 1) = (n + 1) ^ k - 1 - \sum _ {j = 0} ^ {k - 2} \binom{k}{j} \cdot S_n(j) \]

\(k = k + 1\) 便有 \[ (k + 1) \cdot S_n(k) = (n + 1) ^ {k + 1} - 1 - \sum _ {j = 0} ^ {k - 1} \binom {k + 1}{j} S_n(j) \]

\[ S_n(k) = \frac{(n + 1) ^ {k + 1} - 1 - \sum _ {j = 0} ^ {k - 1} \binom {k + 1}{j} S_n(j)}{k + 1} \]

也是 \(O(k ^ 2)\) 递推即可

T3.LUOGUP1415 拆分数列

正着 \(dp\) 一遍求出以 \(i\) 作为结尾字符的递增序列时最小末尾的起始位置

反着 \(dp\) 一遍求出以 \(i\) 作为起始字符的递减序列时最大末尾的结束位置

注意正着 \(dp\) 结束后可能会有前导零, 我们可以贪心的将前导零分到最后一个数字的前面, 因为这样不会改变大小, 但是如果把这些零分到前面的数字后面会使前面的数字变大, 但又因为要小于最后一个数字所以会使答案变劣

最终复杂度 $O(n^3) $

可以预处理出 \(lcp\) 让复杂度降到 \(O(n ^ 2)\)

T4.BZOJ1725 [USACO06NOV]玉米田Corn Fields

状压\(DP\)

\(f_{i,S}\) 表示考虑了前 $i - 1 $ 行, 第 \(i\) 行的状态为\(S\)

预处理一下哪些状态有相邻的草

然后暴力枚举母集, 大力转移就好了

复杂度 \(O(3^n \cdot n)\)

T5.BZOJ1226[SDOI2009]学校食堂

\(f_{i,k,S}\) 表示前 $ i - 1 $ 个同学已经吃了, 上一吃的同学的位置和 \(i\) 同学的位置的差值为 \(k, i\) 同学的后面 \(7\) 个同学的状态为 \(S\)

但是有个很严重的问题我们怎么保证前 \(i - 1\) 个同学都吃了呢 ? 我们只要保证我们转移是合法的就可以了, 所以可能会出现 \(f_i\)\(f_i\) 中的状态转移

所以我们枚举 \(S\) 的时候要从小到大枚举保证不会循环转移

关于转移的话, 我们枚举一下下一个选 \(i\) 号同学后面的第 \(j\) 个同学

  • \(f_{i, k, S} \to f_{i + 1, S >> 1, k - 1}\)\(S \& 1 = 1\)
  • \(f_{i,k,S} \to f_{i,j,S|1<<j}\)\(S\&1\ne1\)

注意能够选的范围是随着你选的人而实时更新的

T6.BZOJ4555[HEOI2016/TJOI2016]求和

\[ f(n) = \sum _ {i = 0} ^ n \sum _ {j = 0} ^ i S(i,j)\times 2^j \times j! \]

求上述式子的值, \(n \le 10^5\)

首先我们得知道当 \(i < j\) 时 $S(i,j) =0 $

所以为了方便我们修改一下上界 \[ f(n) = \sum _ {i = 0} ^ n \sum _ {j = 0} ^ n S(i,j)\cdot 2^j \cdot j! \] 用第二类斯特林数的公式展开一下 \[ S(i, j) = \frac{1}{j!} \cdot \sum _ {k = 0} ^ j (-1) ^ k\cdot \binom{j}{k} \cdot (j - k) ^ i \]

\[ f(n) = \sum _ {i = 0} ^ n \sum _ {j = 0} ^ n 2^j \cdot \sum _ {k = 0} ^ j (-1) ^ k\cdot \binom{j}{k} \cdot (j - k) ^ i \] 交换求和顺序 \[ f(n) = \sum_{j = 0} ^ n 2^j \cdot \sum _ {i = 0} ^ {n} \sum _ {k = 0} ^ j (-1) ^ k \frac{j! \cdot (j - k)^i}{k! \cdot (j - k) !} \]

\[ f(n) = \sum_{j = 0} ^ n 2^j \cdot j! \cdot \sum _ {i = 0} ^ {n} \sum _ {k = 0} ^ j \frac{(-1) ^ k\cdot (j - k)^i}{k! \cdot (j - k) !} \]

\[ f(n) = \sum _ {j = 0} ^ {n} 2^j \cdot j! \cdot \sum_{k = 0} ^ j \frac{(-1) ^ k}{k!} \frac{\sum_{i = 0} ^ {n} (j - k)^i}{(j - k)!} \]

然后设 \[ h(i) = \frac{(-1)^i}{i!} \]

\[ g(i) = \frac{\sum_{j = 0} ^ ni^j}{i!} = \frac{i^n - 1}{(i - 1)i!} \] 特别的关于边界 \[ h(1) = -1, g(0) = 1, g(1) = n + 1 \] 然后 \[ f(n) = \sum _ {j = 0} ^ n 2^j \cdot j! (h * g)(j) \] 跑一遍 \(NTT\) 就好了

T7.LUOGUP1070 道路游戏

\(DP\) 很裸

\(f_i\) 表示第 \(i\) 时刻的最大收益

直接枚举一个时间, 枚举当前时刻在哪个工厂, 往后走几步

则有转移 \[ f_i - c_x + calc(x, i, p) \to f_{i + p} \] 关于 \(calc(x,i,p)\) 表示从在 \(i\) 时刻从 \(x\) 往后走 \(p\) 步的收益, 维护一个前缀和就可以 \(O(1)\) 求出来了

复杂度的 \(O(n ^ 3)\) , 那单调队列搞一搞可以优化成 $ O( n ^ 2 ) $

T8.BZOJ1047 [HAOI2007]理想的正方形

先拿 \(a\) 个单调队列维护一下每行的最值, 并且只考虑 \(n\)

然后把这些单调队列的队头看成一个元素, 用另外一个单调队列去维护这些队头, 从第一行扫到最后一行

然后再移动列的指针维护一下每一行的单调队列的队头就好了, 这样一直循环下去

复杂度 \(O(ab)\)

T9.LUOGUP2219[HAOI2007]修筑绿化带

把每个点的权值看成以这个点为左上角的 \(c \times d\) 的矩阵内的元素的和

然后按照 \(T8\) 的方法搞一下就好了

但是要注意一下边界问题

T10.BZOJ1804[SCOI2005]最大子矩阵

首先 \(O (k \cdot n^4)\) 的暴力 \(DP\) 是可以过去的

我们考虑一下正确的 \(DP\)

\(f_{i,j,S}\) 表示考虑完了前 $i- 1 $ 行选了 \(j\) 个矩阵, 第 \(i\) 行的状态是 \(S (S < 5)\) 时的最大收益

讲一下这个地方的 \(S\) 表示的含义

  • \(S= 0\) 表示这一行空着
  • \(S = 1\) 表示这一行选了第一列, 第二列空着
  • \(S = 2\) 表示这一行选了第二列, 第一列空着
  • \(S = 3\) 表示这一行两个都选了并且这两个都来自同一个矩阵
  • \(S = 4\) 表示这一行两个都选了但这两个来自两个不同的矩阵

知道了状态, 转移就大力讨论一下就好了

如果只有一列的话, 那就把第二列中所有的元素都看成 \(0\) 就好了

注意 : 这个状态的精髓就在于在第 \(i\) 选择的元素, 可以和之间的拼起来, 而不增加矩阵的个数

复杂度 \(O(nk)\)

T11.LUOGUP4918信仰收集

我们可以把瞬移拆成走 \(a\) 步和走 \(b\) 步, 然后考虑 \(dp\)

\(f_{i,k}\) 表示到第 \(i\) 个点还剩 \(k\) 步的最大收益

然后直接在 \(DAG\)\(dp\) 就好了

注意一定要拓扑排序, 不然转移顺序会出问题

复杂度 \(O(n \cdot b)\)

T12.BZOJP1925[SDOI2010]地精部落

\(f_{i, j, 0/1}\) 表示考虑前 \(i\) 个数, 最后一个数为 \(j\) 并且它和上一个数组成的序列是上升或者下降的总方案数

我当时就只想到了这一步, 但是我否定了它, 觉得只考虑前 \(i\) 个好像并不能考虑到所有方案, 但实际上\(f_n\) 是考虑到所有的数了的, 所以并没有问题

然后有转移 \[ f_{i - 1, k, 0} \to f_{i,j, 1} | k < j \] 但考虑到其实你把 \(i \to n + 1 - i\) 会发现其实上升和下降其实是等价的 \[ f_{n, i, 1} = f_{n, n + 1 - i, 0} \] 所以转移变成了 \[ f_{i - 1, i - k, 1} \to f_{i, j, 1} | k < j \] 所以其实最后那一维 \(0/1\) 是多余的

这样复杂度是 $ O(n ^ 3) $ 的

前缀和优化一下就变成了 $ O (n ^ 2) $ 了

T13.BZOJ3126[USACO13OPEN]照片Photo

为啥大家都说这个题是差分约束黑人问号

考虑 \(dp\) , 设 \(f_i\) 表示必须选择第 \(i\) 个点的最优解

然后我们维护一个 \(In[i], Out[i]\)

\(In[i]\) 表示覆盖第 \(i\) 个点的线段的左端点的最小值 - 1

\(Out[i]\) 表示右端点小于 \(i\) 的线段的最端点的最大值

能够所有能够转移到 \(i\)\(j\) 应该满足大于等于 \(Out[i]\) 并且 大于等于 \(In[i - 1]\) 小于等于 $ In[i] $

这个东西维护一个单调队列就好了

T14.LUOGUP2698 [USACO12MAR]花盆Flowerpot

你可以二分一下然后在用单调队列维护一下最大最小值

复杂度 $ O(nlogn) $

但是我们考虑一个更优秀的做法

我们先确定一个左端点, 然后把右端点一直向右移动, 移动到左右端点组成的区间满足条件, 然后移动左端点, 直到不符合条件, 然后跟新答案, 然后这样反复进行下去, 不断的更新答案就好了

可以证明这是对的

复杂度 $ O(n) $

T15.BZOJ4033[HAOI2015]树上染色

考虑 \(dp\)

我一开始想得是 \(f_{i,j}\) 表示以 \(i\) 号节点为根的子树中选 \(j\) 个黑色节点的这颗子树的答案

但是这个 \(dp\) 是有后效性的, 我们考虑换一下状态

\(f_{i,j}\) 表示考虑以 \(i\) 号节点为根的子树中的所有边整颗树的最优贡献

这样就没问题了, 然后我们树上背包一下

注意树上背包的时候要在更新子节点的子树大小之前 \(dp\) , 这样可以保证复杂度的正确性

为什么呢, 这样的话相当于每个节点都只会在 \(LCA\) 处被枚举到, 所以 \(dp\) 的过程相当于枚举了树上的两两点对复杂度为 $ O( n ^ 2 ) $

T16.LUOGUP1410子序列

比较有趣的一道 \(dp\)

我们设 \(f_{i,j,0/1}\) 表示考虑了前 \(i\) 个数字第一个/第二个集合选了 \(j\) 个另一个集合结尾数字的最小值

对于 $ f_{i, j, S} $ 有转移

\(T = S \ xor \ 1\)

  • $f_{i + 1, j + 1, S} = min { f_{ i, j, S } }     if   a_{i + 1} > a_i $
  • $f_{i + 1, i - j + 1, T} = min { a_i }     if   a_{i + 1} > f_{i, j, S} $

相当于在两个串当中相互转换

T17.BZOJ1296[SCOI2009]粉刷匠

考虑到行与行之间互不影响, 我们考虑预处理每行的最优解

\(h[j][k][0/1]\) 表示对于每一行的前 \(j\) 列, 刷了 \(k\) 次, 这一行的第 \(j\) 列刷的是红色或蓝色的最优解

转移显然

\(S (0 / 1), T = S \ \ xor 1\), 行号为 \(i\)

  • \(h[j][k][S] = max(h[j - 1][k][S], h[j - 1][k - 1][T]) + (s[i][j] == S)\)

\(g[i][j]\) 表示第 \(i\) 行刷了\(j\) 次的最优解, \(f[i][j]\) 为前 \(j\) 行, 刷了 \(i\) 次的最优答案

则有转移

  • \(f[i][j] = max(f[i - k][j - 1] + g[j][k])\)

总复杂度 \(O(n \cdot m^2 + Tnm)\)

T18.BZOJ4005[JLOI2015]骗我呢

组合数 + 神仙容斥, 见 Link

T19.BZOJ1190[HNOI2007]梦幻岛宝珠

考虑到每个重量都可以写成 \(a \times 2^b\) 的形式

我们考虑把 \(b\) 相同的宝石放在一起先 \(dp\) 一下

\(f[i][j]\) 表示 \(b = i\) 时, 选出来的宝石的 \(a\) 值的和为 \(j\) 的最大收益, 这个东西跑一下背包就好了

问题在于如何合并

我们再设 \(g[i][j]\) 表示选出来的宝石的重量形如 \(2^i + w \& ((1<<i) - 1)\) 时的最大收益

有转移 : \[ g[i][j] = max \{f[i][j - k] + f[i - 1][min(2 \times k + (w >> i - 1) \& 1, \sum a_i)]\} \] \(PS:\) 注意更新答案的时候要保证状态合法, 因为这个我WA了一年

T20.BZOJ4813[CQOI2017]小Q的棋盘

\(WA\) 又膜了 \(Edt\) 的题解, 我太菜辣, 每天被暴打

首先一个 \(dp\) 数组是没办法表示全部的状态的

我们设 \(f[i][j]\) 表示当前到了 \(i\) 节点, 并且这个子树中走了 \(j\) 要回到 \(i\) 的最大覆盖点数

\(g[i][j]\) 则表示不需要回到 \(i\) 点的最大覆盖点数

则有转移 \[ g[i][j + k + 1] = max\{f[i][k] + g[v][j]\}\\ g[i][j + k + 2] = max\{g[i][k] + f[v][j]\}\\ f[i][j + k + 2] = max\{f[i][k] + f[v][j]\} \] 啊啊啊啊啊啊, 我好菜啊

T21.BZOJ4987Tree

首先我们得知道一个结论

选出来的 \(k\) 个节点一定是一个联通块, 并且答案就是这个联通块中的边权和 \(\times 2\) 减去直径

然后又被 \(Edt\) 秒掉了

因为我不会, 只好去抄一波题解了

考虑 \(dp\) , 设 \(f[i][j][0/1/2]\) 表示在以 \(i\) 为根的子树中选出 \(j\) 个节点的并且在其中确定了 \(0/1/2\) 个直径端点的最优解

转移方程如下 : \[ f[i][k][0] + f[son_i][j][0] + 2 \times w_i \to f[i][k + j][0] \\ f[i][k][1] + f[son_i][j][0] + 2 \times w_i \to f[i][k + j][1] \\ f[i][k][0] + f[son_i][j][1] + w_i \to f[i][k + j][1] \\ f[i][k][1] + f[son_i][j][1] + w_i \to f[i][k + j][2] \\ f[i][k][2] + f[son_i][j][0] + 2 \times w_i \to f[i][k + j][2] \\ f[i][k][0] + f[son_i][j][2] + 2 \times w_i \to f[i][k + j][2] \]

T22.LUOGU2915[USACO08NOV]奶牛混合起来Mixed Up Cows

裸的状压 \(dp\) , 设 \(f[S][i]\) 表示考虑了的牛的集合为 \(S\) , 并且最后一个考虑的为 \(i\)

直接转移就好了 \[ f[S][i] \to f[S \cup \{j\}][j], |h[i] - h[j]| > k \]

T23.BZOJ1293 [SCOI2009]生日礼物

\(T14\) , 拿两个指针扫一下就好辣

T24.BZOJ1855[SCOI2010]股票交易

先考虑暴力 $O(n^3) $ 的 \(dp\)

\(f[i][j]\) 表示考虑了前 $ i $ 天, 手上持有 \(j\) 个股票的最大收益

然后有转移 \[ f[i][j] = f[i - 1][j] \\ f[i][j] = - AP[i] \times j \ \ \ \ \ if(j \le AS[i]) \\ f[i][j] = max\{ f[i - W - 1][j] + AP[i] \times (k - j) | k \in [max(0, j - AS[i]), j]\} \\ f[i][j] = max\{ f[i - W - 1][j] + BP[i] \times (k - j) | k \in [min(j + BS[i], MaxP)]\} \] 发现能转移的区间长度是固定的, 直接单调队列搞一下就好了

详见滑动窗口

T25.BZOJ4591[SHOI2015]超能粒子炮·改

这题比较有趣, 题意就是求一下下面这个式子的值 \[ \sum_{i = 0}^k \binom{n}{i} \pmod{2333} \ \ n, k \le 10^{18} \] 考虑卢卡斯定理, 那么式子变成了这样(设 \(P = 2333\)) \[ \sum_{i = 0} ^ k \binom{n \% P}{i \% P} \cdot \binom{\frac{n}{P}}{\frac{i}{p}} \pmod{P} \] 因为模运算是有循环节的, 考虑把相同的部分提出来, 那么变成了这样 \[ \sum _ {j = 0} ^ {p - 1} \binom{n \% P}{j} \sum _ {i = 0} ^ {\frac{k}{P} - 1} \binom{\frac{n}{P}}{i}+ \binom{\frac{n}{P}}{\frac{k}{P}} \cdot\sum _ {i = 0} ^ {k \% P} \binom{n \% P}{i} \] 然后我们设 \(f[n][k] = \sum_{i = 0} ^ k \binom{n}{i}\)

然后上述式子就变成了 \[ f[n][k] = f[n \% P][p - 1] \cdot f[\frac{n}{P}][\frac{k}{P} - 1] + \binom{\frac{n}{P}}{\frac{k}{P}} \cdot f[n \% P][k \% P] \] 然后这个是个递归式, 就递归一下就好了

我们可以先处处理出 $n, k < P $ 的 \(f\) 值, 那么递归条件就是 \(n < P \ \ and \ \ k < P\)

注意当 \(k < 0\) 时, 这个式子的值是 \(0\)

T26.BZOJ5278[USACO18OPEN]Out of Sorts Gold

我又再一次的抄了题解, 太菜辣

然而看题解还看不懂, 最终在 \(Edt\) 的帮助下我终于搞明白了这道题

考虑一下题面里给的那个东西到底在干嘛, 其实每进行一次这个操作, 对于一个前缀 \([1, r]\) 把排序后本不在这个区间内值移到后面这个 \([r + 1, n]\) 去, 把一个小的换进来

所以我们直接对于每一个前缀的不属于这个前缀的数的个数取个 \(max\) 就好辣

T27.BZOJ5280[Usaco2018OPEN]Milking Order

假如我们不考虑是否合法的问题

我们要知道这道题其实做一个 \(Toposort\) 就好了

那么其实不合法的情况就是这个图里有环, 我们考虑二分一个位置使得将前面所有的边都加入图中都不产生环就好了

T28.BZOJ5281[Usaco2018 Open]Talent Show

\(01\) 规划裸题

二分 + 背包就好辣

T29.BZOJ2820 YY的GCD

\[ f(d) = \sum _ {x \in [1, a], y \in [1, b]} [gcd(x, y) = d] \\ F(d) = \sum _ {x \in [1, a], y \in [1, b]} [d \ \ | \ \ gcd(x, y)] \]

我们要求这个东西 \[ \sum _ {P \in Prime} f(P) \\ \sum _ {P \in Prime} \sum _ {P | d} \mu(\frac{d}{P}) F(d) \\ \] 因为 \(F(d) = \lfloor \frac{a}{d} \rfloor \lfloor \frac{b}{d} \rfloor\)

可得 \[ \sum _ {P \in Prime} \sum _ {P | d} \mu(\frac{d}{P})\lfloor \frac{a}{d} \rfloor \lfloor \frac{b}{d} \rfloor \\ \] 我们在设 \[ G(n) = \sum _ {P \in Prime, P | n} \mu(\frac{n}{P}) \] 然后再将 \(G(x)\) 代入上一个式子 \[ \sum _ {d} Q(d)\lfloor \frac{a}{d} \rfloor \lfloor \frac{b}{d} \rfloor \] 推到这里大概也就差不多了

至于具体做法, 就是将 \(Q\) 这个东西预处理出来, 然后对于每个询问就整除分块一下可以做到 \(O(\sqrt{n})\) 的复杂度

然后我们来讨论一下预处理 \(Q\) 的两种做法

  1. 我们直接大力枚举素数, 然后再枚举素数的倍数, 虽然枚举倍数是调和级数, 但是我们只枚举了素数的倍数, 所以根本跑不满, 实测跑得飞快, 复杂度 \(O(玄学)\)
  2. 我们考虑能否直接在线性筛的时候, 直接求出 \(Q\)

设当前枚举到 \(i\) , 正在用 \(P_0\) 这个素数去筛, \(v = i \times P_0\)

\[ Q(v) = \mu(i) + \sum _ {P \in Prime, P | i, P \ne P_0} \mu(\frac{i}{P} \times P_0) \]

分两种情况讨论一下

如果 \(P_0 | i\) 因为 \(P \ne P_0\) 所以对于任意的 \(\mu(\frac{i}{P} \times P_0)\) , 它的值都为零, 因为 \(P_0\) 的幂次数肯定大于 \(1\)

所以 \(Q(v) = \mu(i)\)

如果 \(P_0 \not| i\)

因为 \(\mu\) 是一个积性函数, 且 \(gcd(\frac{i}{P}, P_0) = 1\)

所以 \(\mu (\frac{i}{P} \times P_0) = \mu(\frac{i}{P}) \times \mu(P_0)\)

则有 \[ Q(v) = \mu(i) + \mu(P_0) \times \sum _ {P \in Prime, P | i} \mu(\frac{i}{P}) \\ Q(v) = \mu(i) - Q(i) \] 综上所述 \[ Q(v) = \mu(i) - Q(i) \times [gcd(i, P_0) = 1] \] 知道这个以后, 我们就可以用线性的复杂度求出 \(Q\)

所以最优总复杂度为 \(O(n + T\sqrt{a})\)

T30. BZOJ2301 HAOI2011 Problem B

BZOJ1011 ZAP 的思路上加一个容斥就好了

具体的, 我们设 \[ f(a, b, k) = \sum _ {x \in [1, a], y \in [1, b]} [gcd(x, y) = k] \\ \] 则答案为 \[ f(b, d, k) - f(a - 1, d, k) - f(c - 1, b, k) + f(a - 1, c - 1, k) \] 至于求 \(f(n, m, k)\) 的话反演一下就好了

复杂度 \(O(T \sqrt{n})\)

T31. BZOJ2809 Gty的二逼妹子序列

一个裸的莫队

与以往不一样的是, 我们在移动莫队的指针时要支持维护一个区间和, 考虑到修改的次数和移动的次数不在一个数量级上, 修改的次数要比查询的次数要多得多, 所以我们考虑一个可以支持 \(O(1)\) 修改, 但查询复杂度没那么优秀的数据结构

我们考虑分块!

这样就可以让修改的复杂度降到 \(O(1)\) 了, 但查询是 \(O(\sqrt{n})\)

总复杂度为 \(O(m\sqrt{n})\) 的, 相比用树状数组的复杂度 \(O(m \sqrt{n} \cdot logn)\) 还是要优秀很多的

T32. LUOGU4949最短距离

给你一颗基环树, 要求支持修改边权和查询两点之间最短距离

首先我们要建一颗生成树, 记多余的那条边为 \((x_0, y_0, w_0)\)

那么两点 \((x, y)\) 之间的最短距离则为 \[ min (dis_{x, y}, dis_{x, x_0} + dis_{y_0, y} + w_0, dis_{x, y0} + dis_{x_0, y} + w_0) \] 如果带修改的话, 树剖肯定是可以维护的

我们考虑一个更优秀的做法, 我们维护每个节点到根节点的距离 每次修改一条边的边权相当与把这条边连接的两个端点中深度较深的那个点的子树中的所有点到根节点的距离都修改, 在 \(dfs\) 上的体现就是一段连续的区间, 所以用树状数组维护一下差分就好辣

T33.BZOJ2742 HEOI2012 Akai的数学作业

因为题目只要求我们求出有理数解, 所以如果这个高次方程有有理数解的话, 则一定可以被表示形如下述式子的样子

\[ (P_1x + P'_1)(P_2x + P'_2) \cdots (P_nx + P'_n)(无法被分解的式子) = 0 \] 其中 \(P_i\) 为最高次项系数的因数, \(P'_i\) 为常数项的因数

所以我们只用把最高次项的系数的因数和常数项的因数两两配对以下, 如果该解带入方程成立, 则说明我们找到了一个符合题目要求的解

有个小细节就是, 常数项可能为零, 所以我们把次数最低且系数不为零的那一项看做常数项就好了

\(Trick\) : 当我们想判断极大的数是否相等时, 只要多取几个膜数, 判断它们在膜意义下相不相等即可

T34.BZOJ3236 AHOI2013作业

解法同 BZOJ2809 Gty的二逼妹子序列

T35.BZOJ5020 THUWC2017在数学王国中畅游

主要考察数学

我们考虑如果只有一次函数的话, 我们维护一下系数和, 和常数项和就好了

但是如果换成三角函数, 和指数函数的话该怎么搞呢?

我们注意到题面给的那个式子 \[ f(x) = \sum _ {i = 0} ^ {+\infty} \frac{f^{(i)}(x_0)(x - x_0) ^ i}{i !} \]

其实就是暗示我们去维护一个多项式, 然后维护这个多项式的每一项的系数和, 就可以做到快速维护和

由于这道题对精度的要求并没有那么高, 所以我们只用维护 \(13 \sim 15\) 项就可以保证精度了

至于题目要求我们维护一个森林里的两个点之间的函树值的和, 那就 \(LCT\) 搞一搞就好了, 每次 \(update\) 的复杂度均为 \(O(15)\) 总复杂度为, 所以总复杂度为 \(O(15 \cdot nlogn)\)

T36.BZOJ5343 CTSC2018混合果汁

首先容易想到是二分, 我们可以二分一个答案, 问题在于如何 \(check\) 我们考虑按照果汁美味程度的从大到小的顺序来建一颗主席树, 每次往主席树上插点时, 是按照价格大小排序的, \(check\) 的话就直接在主席树上贪心二分就好了

T37.BZOJ2818 GCD

要求求出 \[ \sum _ {x, y \le n} [gcd(x,y) = 1] \] 因为 \(x, y\) 的上限是一样的所以这题其实并不需要莫比乌斯反演, 其实直接用 \(\varphi\) 搞一下就好了

答案为 \[ \sum _ {P \in Prime} \sum _ {P | d} \varphi(d) \] 这样直接暴力搞其实也是可以 \(A\) 的, 但是我们考虑一下更优秀的做法, 我们可以直接维护一下 $$ 的前缀和 \(S\), 所以 \[ \sum _ {P | d} \varphi (d) = S(\lfloor \frac{n}{P} \rfloor) \] 所以最终总复杂度为 $ O(n) $

T38.LUOGU四元组统计

给定大小为 \(n\) 的集合 \(A\) , 要求求出 \(gcd(A_i, A_j, A_k, A_l) = 1\) 的个数 \[ f(d) = \sum _ {a, b, c, d \in A} [gcd(a, b, c, d) = d] \\ F(d) = \sum _ {a, b, c, d \in A} [d \ \ | \ \ gcd(a, b, c, d)] \]

这个东西直接反演就好了

\[F(d) = \binom{\sum _ {i} [d | A_i]}{4}\]

T39.BZOJ1052 HAOI2007覆盖问题

考虑直接二分一个 \(L\), 但是这道题的 \(check\) 有点不太好想

我们考虑一个问题 : 对于一个点集 \(S\) , 存在一个覆盖这 \(|S|\) 个点的最小矩形, 必定有一个正方形的顶角和这个最小矩形的顶角重合, 其实这个结论也很好证明, 因为这个矩形是最小矩形, 所以矩形的四条边界上至少会有四个点, 所以至少有一个正方形横跨了矩形的两条边, 所以必定有一个正方形的顶角和这个最小矩形的顶角重合

然后我们 \(check\) 的话就直接 \(dfs\) 一下就好了

$PS : $ 每次确定一个正方形后会覆盖一些点, 然后需要重新更新这个最小矩形

T40.BZOJ1863 ZJOI2006皇帝的烦恼

首先当 \(n\) 是偶数时我们直接输出相邻的 \(a\) 值和的最大值就好了

但如果 \(n\) 是奇数时, 这个结论就不成立了

我们考虑二分一个答案 \(M\), 然后用 \(dp\)\(check\)

因为这个结论不成立是因为最后一个将军可能会和第一个将军产生冲突, 所以我们设

\(f[i]\) 表示第 \(i\) 个将军和第 \(1\) 个将军最少有多少个相同的颜色

\(g[i]\) 表示第 \(i\) 个将军和第 \(1\) 个将军最多有多少个相同的颜色

则有转移 \[ g[i] = min(a[i], a[1] - f[i - 1]) \\ f[i] = max(0, a[i] - (M - a[1] - (a[i - 1] - g[i - 1]))) \] 对于 \(g\) 的转移很显然, 我在这里就解释一下 \(f\) 的转移式为什么是这个, 如图

T41.BZOJ3529 SDOI2014数表

首先能整除 \(i, j\) 的数的集合等于能整除 \(gcd(i, j)\) 的数的集合, 所以

\[ f(d) = \sum _ {x \in [1, n], y \in [1, m]} [gcd(x, y) = d] \\ F(d) = \sum _ {x \in [1, n], y \in [1, m]} [d \ \ | \ \ gcd(x, y)] \\ G(n) = \sum _ {d | n} d \]

则答案为

\[ ans = \sum _ {P} G(P) f(P) \\ ans = \sum _ {P} G(P) \sum _ {P | d} \mu (\frac{d}{P}) F(d) = \sum _ {P} G(P) \sum _ {P | d} \mu (\frac{d}{P}) \lfloor\frac{n}{d}\rfloor \lfloor\frac{m}{d}\rfloor \]

我们再设 \[ S(n) = \sum _ {d | n} \mu(\frac{n}{d})G(d) \] 所以 \[ ans = \sum _ {d} S(d)\lfloor\frac{n}{d}\rfloor \lfloor\frac{m}{d}\rfloor \] 如果没有第三个限制, 那么做到这里就直接做完了, 但是要求所有被统计的 \(G(d) \le k\) , 所以我们离线一下询问, 将所有的询问按 \(k\) 值排序, 将所有的 \(G(d)\) 排序, 然后指针扫一遍就好了, 又因为整除分块要用到 \(S(d)\) 的前缀和, 所以那个树状数组维护一下 \(S(d)\) 的前缀和就好了

最后关于 \(G(d)\) 求法, 我们可以在线性筛的时候求, 下面给出式子

设当前枚举到 \(i\) , 正在用 \(P_0\) 这个素数去筛, \(v = i \times P_0\) \[ G(v) = \begin{cases} G(i) \times (P_0 + 1) ~~~~~~~~~~~~if ~~v \not| \ \ i\\ G(i) + G(\frac{i}{P_0^k}) \times P_0^k ~~~~~if ~~ v \ \ | \ \ i \ \ and \ \ gcd(\frac{i}{P_0^k}, P_0^k) = 1 \ \ and \ \ k > 0\end{cases} \]