当前位置：首页 > news >正文

趣题记

news 2025/10/4 0:25:31

收录了一些很可爱的题呢。

有些写了题解有些没写，所以长短不一，能不贴代码我也尽量不贴，让长度短一点。

CF622F

拉格朗日插值

求 $\sum_{i = 1}^{n} i^k$，$n \le 10^9, k \le 10^6$。

感性理解一下，当 $k$ 为 $1$ 的时候，有公式：$\frac{n \times (n + 1)}{2}$ 是一个二次多项式。

$k$ 为 $2$ 时，有公式：$\frac{n \times (n + 1) \times (2n + 1)}{6}$，是一个三次多项式。

$k$ 为 $3$ 时，有公式：$\left[ \frac{n \times (n + 1)}{2} \right]^2$，是一个四次多项式。

那么 $\sum_{i = 1}^{n} i^k$ 就是一个 $k + 1$ 次多项式。

取 $k + 2$ 个点做拉格朗日插值法可得其关于 $n$ 的多项式 $f(n)$。

把 $n$ 带进去即可，时间复杂度 $\mathcal O(k^2\log k)$。

然而，复杂度仍然是不对的。

观察到我们取的 $k + 2$ 个点是不确定的，所以我们可以钦定第 $i$ 个点取 $(i, \sum_{j = 1} ^ {n}j^k)$，令其表示为 $(i, x_i)$。

那么我们列出最终的多项式：

\[f(n) = \sum_{i = 1} ^ {k + 2}x_i\prod_{1 \le j \le k + 2, j \ne i}\frac{n - j}{i -j} \]

我们发现后面这一大坨非常可算啊。

只看后面的这一部分：

\[\begin{align*} &\\ \prod_{1 \le j \le k + 2, j \ne i}\frac{n - j}{i -j} &= \frac{\prod_{1 \le j \le k + 2, j \ne i}(n - j)}{\prod_{1 \le j \le k + 2, j \ne i}(i -j)}\\ &= \frac{\prod_{1 \le j \le k + 2, j \ne i}(n - j)}{\prod_{1 \le j \le i - 1}(i - j) \times \prod_{i + 1 \le j \le k + 2}(i - j)}\\ &= \frac{\prod_{1 \le j \le k + 2, j \ne i}(n - j)}{(i - 1)\times(i - 2) \times \dots \times 1 \times (-1) \times (-2) \times \dots \times (i - k - 2)} \\ &= \frac{\prod_{1 \le j \le k + 2, j \ne i}(n - j)}{(i - 1)! \times (k + 2 - i) ! \times (-1)^{k + 2 - i}}\\ &= \frac{\prod_{1 \le j \le i - 1}(n - j) \times \prod_{i + 1 \le j \le k + 2}(n - j)}{(i - 1)! \times (k + 2 - i) ! \times (-1)^{k + 2 - i}} \end{align*} \]

分母可以通过预处理解决，而分子则可以拆成前缀、后缀积。

然后 $-1$ 的次方真的不用快速幂啊。

那么时间复杂度就来到了 $\mathcal O(k\log k)$，足以通过此题。

CF559E

老师布置杂题的时候做的这题，居然做出来了，不敢相信。

CF*3000，div 1，E 题

dp

最开始考虑记录 $f_{i, (0/1)}$ 为前 $i$ 个线段且第 $i$ 个线段朝左（右）的最大覆盖。

发现这样状态简单但是转移十分困难。难点在我们不知道前 $i - 1$ 个的朝向，如果要硬记就要状压，放弃吧。

我们发现我们实际关心的并不是前 $i - 1$ 个的状态而是最靠右边的线段。

那么可以考虑改状态为 $f_{i, j, (0 / 1)}$ 代表前 $i$ 条线段中第 $j$ 条线段最靠右且朝向左（右），并且第 $i$ 条线段的朝向对于转移的影响不大所以直接不记。

先对所有线段按左端点排序。

刷表法。

考虑 $f_{i, j, p}$ 能影响到哪些位置。枚举 $k \in [i + 1, n]$，$l \in \{0, 1\}$，沿途顺便计算最靠右的位置，记为 $K, L$。

那么 $f_{i, j, p}$ 就能影响到 $f_{k, K, L}$。

我们发现，因为我们排过序，所以 $a_K \le a_k$，又因为 $a_K + L \times l_K$ 最大，所以 $a_k + d \times l_k$ 到 $a_K + L \times l_K$ 的区域是连续的（$d$ 是现在对于 $k$ 枚举的方向）。

再来看从 $a_j + p \times l_j$ 到 $a_k + d \times l_k$ 的贡献，这个值最大为 $l_k$，那么贡献为 $\min(l_k, (a_k + d \times l_k) - (a_j + p \times l_j))$。

\[f_{i, j, p} + (a_K + L \times l_K) - (a_k + d \times l_k) + \min(l_k, (a_k + d \times l_k) - (a_j + p \times l_j)) \to f_{k, K, L} \]

注意它的值域是 $[-10^8, 10^8]$ 而不是 $[0, 10^8]$，所以最小值不要设置成 $0$。

P8868

线段树，还挺好想。

求：

\[\sum_{p = l} ^ {r} \sum_{q = p} ^ {r} \left ( \max_{i = p} ^ {q} a_i \right )\left ( \max_{i = p} ^ {q} b_i \right ) \]

看到区间套区间，自然想到在线不是很好做，又没有强制在线，考虑离线结合扫描线。

扫描右端点 $r$，动态维护后缀最大值 $x$ 和 $y$。显然可以单调栈维护，这样区间取最大值操作就变成了区间覆盖操作。

然后我们还需要记一个答案数组 $s_i$，代表查询区间 $[i, r]$ 的答案。

那么对于每次更新，$s_i$ 都会加上一个值 $x_iy_i$，注意不是赋值。然后维护区间 $s$ 数组的和。

最后统计一下答案即可。

相比于做法，这题标记的打法更难想。

我们并不考虑在更新 $x$、$y$ 的同时更新 $s$，这样就会更好处理。

即完成以下步骤：

区间覆盖 $x$。
区间覆盖 $y$。
更新 $s$。

首先我们需要 $x$、$y$ 的覆盖标记和 $xy$ 更新 $s$ 的倍率，记作 $t_x$、$t_y$、$s_{xy}$。

更新 $s$ 的优先级高于 $x$、$y$，因为如果上一次更新 $s$ 还没有操作就已经完成了下一次覆盖，那么上一次的答案将无法计算。

看起来很和谐，是不是？但是有一个问题，就是如果 $x$、$y$ 的标记已经下传，此时更新 $s$ 的区间的 $x$、$y$ 不一定是全部相等的，这就意味着 $s$ 的更新是错误的。

加入新标记 $s_x, s_y, s_1$ 分别代表 $x, y, 1$ 更新 $s$ 的倍率，与此同时，需要记录 $x$、$y$、$xy$ 的和，记为 $c_{x}, c_{y}, c_{xy}$。

标记更新标记，设被更新的标记下标为 $u$：

转移见代码。

::::info[代码]

namespace code {const int N = 2.5e5 + 5;int t, n, q, a[N], b[N], la[N], lb[N], ans[N];struct node {int r, id;};vector< node > qu[N];
// segment tree
#define ls (u << 1)
#define rs (u << 1 | 1)struct TAG {int ali_X = 0, ali_Y = 0, sum_X = 0, sum_Y = 0, sum_XY = 0, sum_1 = 0;TAG() {}TAG(int a, int b, int c, int d, int e, int f): ali_X(a), ali_Y(b), sum_X(c), sum_Y(d), sum_XY(e), sum_1(f) {}operator bool() const {return ali_X || ali_Y || sum_X || sum_Y || sum_XY || sum_1;}};int sum_X[N << 2], sum_Y[N << 2], sum_XY[N << 2], sum_S[N << 2];// X 和、Y 和、XY 和、区间长度、S 和TAG tag[N << 2];void up(int u) {sum_X[u] = sum_X[ls] + sum_X[rs], sum_Y[u] = sum_Y[ls] + sum_Y[rs];sum_XY[u] = sum_XY[ls] + sum_XY[rs], sum_S[u] = sum_S[ls] + sum_S[rs];}void modi(int u, int L, int R, TAG t) {auto &[ali_X, ali_Y, t_sum_X, t_sum_Y, t_sum_XY, t_sum_1] = tag[u];if (ali_X && ali_Y)t_sum_1 += t.sum_XY * ali_X * ali_Y + t.sum_X * ali_X +t.sum_Y * ali_Y + t.sum_1;else if (ali_X)t_sum_1 += t.sum_X * ali_X + t.sum_1,t_sum_Y += t.sum_XY * ali_X + t.sum_Y;else if (ali_Y)t_sum_1 += t.sum_Y * ali_Y + t.sum_1,t_sum_X += t.sum_XY * ali_Y + t.sum_X;elset_sum_X += t.sum_X, t_sum_Y += t.sum_Y, t_sum_XY += t.sum_XY,t_sum_1 += t.sum_1;if (t.ali_X) ali_X = t.ali_X;if (t.ali_Y) ali_Y = t.ali_Y;sum_S[u] += t.sum_XY * sum_XY[u] + t.sum_X * sum_X[u] +t.sum_Y * sum_Y[u] + t.sum_1 * (R - L + 1);if (t.ali_X && t.ali_Y) {sum_XY[u] = t.ali_X * t.ali_Y * (R - L + 1);sum_X[u] = t.ali_X * (R - L + 1);sum_Y[u] = t.ali_Y * (R - L + 1);} else if (t.ali_X) {sum_XY[u] = t.ali_X * sum_Y[u];sum_X[u] = t.ali_X * (R - L + 1);} else if (t.ali_Y) {sum_XY[u] = t.ali_Y * sum_X[u];sum_Y[u] = t.ali_Y * (R - L + 1);}}void down(int u, int L, int R) {if (! tag[u]) return;int mid = (L + R) >> 1;modi(ls, L, mid, tag[u]), modi(rs, mid + 1, R, tag[u]);tag[u] = TAG(0, 0, 0, 0, 0, 0);}void upt(int u, int L, int R, int l, int r, TAG t = TAG(0, 0, 0, 0, 0, 0)) {if (L > r || R < l) return;if (l <= L && R <= r) return modi(u, L, R, t);int mid = (L + R) >> 1;down(u, L, R), upt(ls, L, mid, l, r, t), upt(rs, mid + 1, R, l, r, t);up(u);}int que(int u, int L, int R, int l, int r) {if (L > r || R < l) return 0;if (l <= L && R <= r) return sum_S[u];int mid = (L + R) >> 1;return down(u, L, R), que(ls, L, mid, l, r) + que(rs, mid + 1, R, l, r);}//void init() {}void clear() {}void solve() {cin >> t >> n;L(i, 1, n) cin >> a[i];L(i, 1, n) cin >> b[i];a[0] = b[0] = INT_MAX;cin >> q;L(i, 1, q) {int l, r;cin >> l >> r;qu[r].push_back({l, i});}stack< int > A, B;L(i, 1, n) {la[i] = i, lb[i] = i;while (a[i] > a[la[i] - 1]) la[i] = la[la[i] - 1];while (b[i] > b[lb[i] - 1]) lb[i] = lb[lb[i] - 1];}L(i, 1, n) {upt(1, 1, n, la[i], i, TAG(a[i], 0, 0, 0, 0, 0));upt(1, 1, n, lb[i], i, TAG(0, b[i], 0, 0, 0, 0));upt(1, 1, n, 1, i, TAG(0, 0, 0, 0, 1, 0));for (auto [j, id] : qu[i]) ans[id] = que(1, 1, n, j, i);}L(i, 1, q) cout << ans[i] << "\n";}
}  // namespace code

::::

P6624

poly、矩阵树定理、莫比乌斯反演

本质上可以将此题分成两个部分。

$\mathbf 1.$ 合并代价

代价为两种代价乘起来的并不好（或是不能）算生成树，我们考虑将两个代价之和转化为对每一条便来说的代价之和。

那么这一部分可以直接看作一个莫反，直接使用莫反老套路。

\[\begin{align*} &= \sum_{T \subseteq E, |T| = n - 1} \sum _{i \in T} w_i \times \gcd_{i \in T} w_i\\ &= \sum_{T \subseteq E, |T| = n - 1}\sum _{i \in T} w_i \times \sum_{d | \gcd_{i \in T} w_i} \varphi(d)\\ &= \sum_{d = 1} ^ {N} \varphi(d) \sum _ {T \subseteq E, |T| = n - 1} \left[ d \mid \gcd_{i \in T} w_i \right] \sum_{i \in T} w_i \end{align*}\\ \]

就结束了，预处理 $\varphi$ 函数，枚举 $d$ 加入所有边权为 $d$ 的倍数的边，以 $w_i$ 为边权找所有最小生成树权值和。

$\mathbf 2.$ 最小生成树权值和

矩阵树算法，一个高级的人发明的高级算法可以将线代和图论生成树结合起来，凡人不懂。

运用了机构老师讲的高妙的乘法转加法做法。

::::info[乘法转加法]{open}
记 $x(a_k, a_{k - 1}, \dots, a_0)$ 为多项式 $\sum_{i = 0} ^ {k} a_k \times x ^ k$。

那么：

\[x(a, 1) \times x(b, 1) = x(a b, a + b, 1) \]

忽略二次项答案就是 $x(a + b, 1)$，所以可以用仅保留常数项和一次项的多项式实现乘法转加法。
::::

正常的矩阵树算法是求解：

\[\sum_{T \subseteq E, |T| = n - 1} \prod _ {i \in T} w_i \]

实际上我们要求：

\[\sum_{T \subseteq E, |T| = n - 1} \sum _ {i \in T} w_i \]

区别就在累乘和累加，考虑把 $w_i$ 替换成多项式 $x(w_i, 1)$。

最后直接上矩阵树算法即可。

P7738

cute，很难想象我能想出来。

题目大意：给出 $n$ 个随机生成的 $\textbf {256}$ 位 $01$ 串，$q$ 次询问，每次给定一个不随机生成的 ${256}$ 位 $01$ 串，询问是否有一个串与询问串的汉明距离不超过 $k$。

比较乱搞，不知道是不是正解。

首先，如果询问串也随机生成（即 $16,17,18$ 测试点），那么询问大概率都是 $0$，因为存在汉明距离不超过 $k$ 的概率极低，这是显然的。

观察到 $k \le 15$，我们可以考虑依靠鸽笼原理分块。将 $256$ 位 $01$ 串分成 $16 \times 16$ 的形式，就变成了 $2^{16}$ 进制下的 $16$ 位数。

根据鸽笼原理，满足汉明距离不超过 $15$ 的两个 $01$ 串一定在 $2^{16}$ 进制下有一位相同。

考虑枚举第 $i$ 位相同，此时待选的 $01$ 串个数就是 $\left\lceil\frac{n}{2^{16}}\right\rceil = \left\lceil \frac{4 \times 10^5}{2^{16}} \right\rceil = 7$，直接暴力判断汉明距离即可。

具体实现方面，每个 $01$ 串都可以用一个 $256$ 位的 bitset 存储，查找待选 $01$ 串就用 vector 解决，不用 map，少一个 $\log$。

时间复杂度（差不多是）：

\[\mathcal{O}\left(\frac{m \times 16 \times \frac{n}{L} \times 16}{\omega} \right) = \mathcal{O}\left(\frac{nm}{\omega \times L} \right) ~~ \text{or} ~~ \mathcal{O}\left(\frac{nm}{L} \right) \]

P5072

这就不仅是 kawayi 了，Ynoi 不是开玩笑的。

题目大意：（不用）

莫队

结论猜到了，赢。

在一个长度为 $a$ 的序列中，一个数出现次数为 $b$。则有 $2^{a−b}$个子序列不包含该元素，它的贡献是 $2^a−2^{a−b}$ （摘自尺子姐姐题解）。

猜到了就光速幂套莫队呗。

P5137

题目大意：求

\[\sum_{i = 0} ^ {n} a^ib^{n-i} \bmod p \]

逆天卡常题。

真服了至死没卡过，只好借鉴别人的卡常方法卡过了。

本来就不难想，看到 $n$ 极大、多测就联想到矩阵快速幂。

然后直接列转移方程：

\[f_n = a f_{n - 1} + b ^ {n} \]

直接列矩阵比较困难，考虑设一个辅助转移数组 $g_i = b^i$。

\[ \left( \begin{array}{ccc} f_{n - 1} & g_{n - 1}\end{array} \right) \times \left( \begin{array}{ccc} a & 0 \\b & b\end{array} \right) = \left( \begin{array}{ccc} f_n & g_n\end{array} \right) \]

然后直接转移。

然而这样会超时，如何卡常？

快读快写等不动脑子的都加上。
将向量也看作 $2 \times 2$ 的矩阵，此时所有矩阵右上角元素都为 $0$，省略。
不用 int128，使用抽象方式做乘法。
少用函数。
快速幂写递推而非递归。

P4572

dp。

难度虚高。

题目大意：link。

严格来说算 dp 但是做的时候没想这么多。

首先答案一定具有单调性，二分人数 $k$。

考虑最坏情况是什么，即汤姆·里德尔从树根走向一个叶子结点，那么途中的所有结点的所有子结点都应该被保护。

所以策略就是汤姆·里德尔每走一步就把他的目的地的所有儿子都保护起来。

然而有时候一个结点的所有儿子数量超过了人数，此时就需要用祖先处剩余的次数来保护。

那么我们记 $d_u$ 为结点 $u$ 的这棵子树的所有结点都被保护所需要的祖先处剩余次数总和。

即：

\[d_u = \max(0, c_u - k) + \max\left(0, c_u - k + \sum_{v \in S_u}d_v\right) \]

其中 $c_u$ 为 $u$ 的儿子数量，$S_u$ 为 $u$ 的儿子集合。

check 就返回 $d_1$ 是否为 $0$（即根节点是否需要剩余次数）即可。

P14139

猜结论、Pollard-Rho、质数筛、数学（仅证明）。

事实上我赛时结论是猜的。

题目大意：求

\[\sum_{x=1}^{n} \left\lfloor \frac{x^2}{n} \right\rfloor + \left\lfloor \sqrt{nx} \right\rfloor \]

本题解仅用于证明结论：

\[\sum_{x=1}^{n} \left\lfloor \frac{x^2}{n} \right\rfloor + \left\lfloor \sqrt{nx} \right\rfloor = n^2 + \prod p_i ^ {\lfloor e_{i} / 2 \rfloor} \]

证明如下：

设 $ n = \prod p_i^{e_i} $，其中 $ p_i $ 为质数，$ e_i $ 为正整数。定义 $ m = \prod p_i^{\lfloor e_i / 2 \rfloor} $。

考虑集合 $ S = {1, 2, \dots, n} \times {1, 2, \dots, n} $，则 $ |S| = n^2 $。

定义集合：

$ P = \left{ (x, y) \in S \mid y \leq \frac{x^2}{n} \right} $，则 $ |P| = \sum_{x=1}^{n} \left\lfloor \frac{x^2}{n} \right\rfloor $。
$ Q = \left{ (x, y) \in S \mid y \leq \sqrt{nx} \right} $，则 $ |Q| = \sum_{x=1}^{n} \left\lfloor \sqrt{nx} \right\rfloor $.

需证 $ |P| + |Q| = n^2 + m $.

首先，注意到 $ |P| = \left| \left{ (x, y) \in S \mid x^2 \geq n y \right} \right| $，因为 $ y \leq \frac{x^2}{n} $ 等价于 $ n y \leq x^2 $.

其次，由对称性，$ |Q| = \left| \left{ (x, y) \in S \mid y^2 \leq n x \right} \right| = \left| \left{ (x, y) \in S \mid x^2 \leq n y \right} \right| $。

令 $ u = \left| \left{ (x, y) \in S \mid x^2 \leq n y \right} \right| $，则 $ u = |Q| $.

现在，考虑集合 $ { (x, y) \in S \mid x^2 \geq n y } $ 和 $ { (x, y) \in S \mid x^2 \leq n y } $。它们的并集为 $ S $，且交集为 $ { (x, y) \in S \mid x^2 = n y } $。因此：

\[\left| \left\{ x^2 \geq n y \right\} \right| + \left| \left\{ x^2 \leq n y \right\} \right| = |S| + \left| \left\{ x^2 = n y \right\} \right| = n^2 + \left| \left\{ x^2 = n y \right\} \right|. \]

即：

\[|P| + u = n^2 + \left| \left\{ x^2 = n y \right\} \right|. \]

代入 $ u = |Q| $，得：

\[|P| + |Q| = n^2 + \left| \left\{ x^2 = n y \right\} \right|. \]

现在计算 $ \left | \left{ (x, y) \in S \mid x^2 = n y \right} \right| $。由 $ x^2 = n y $ 可得 $ y = \frac{x^2}{n} $。由于 $ y $ 为整数，$ n $ 必须整除 $ x^2 $，即 $ n \mid x^2 $。同时 $ y \leq n $，故 $ \frac{x^2}{n} \leq n $，即 $ x^2 \leq n^2 $，所以 $ x \leq n $。因此：

\[\left| \left\{ (x, y) \in S \mid x^2 = n y \right\} \right| = \left| \left\{ x \in \{1, 2, \dots, n\} \mid \left(n \mid x^2\right) \right\} \right|. \]

因为 $ n = \prod p_i^{e_i} $，所以 $ n \mid x^2 $ 当且仅当对于每个 $ i $，有 $ e_i \leq 2\alpha_i $，其中 $ x = \prod p_i^{\alpha_i} $。即 $ \alpha_i \geq \lceil e_i / 2 \rceil $。令 $ d = \prod p_i^{\lceil e_i / 2 \rceil} $，则 $ x $ 必须是 $ d $ 的倍数。注意到 $ m = \prod p_i^{\lfloor e_i / 2 \rfloor} $，且 $ d \cdot m = \prod p_i^{\lceil e_i / 2 \rceil + \lfloor e_i / 2 \rfloor} = \prod p_i^{e_i} = n $，所以 $ d = n / m $。因此，满足 $ n \mid x^2 $ 的 $ x $ 即为 $ d $ 的倍数，且 $ x \leq n $，故这样的 $ x $ 的个数为 $ \lfloor n / d \rfloor = \lfloor n / (n / m) \rfloor = \lfloor m \rfloor = m $。因此：

\[\left| \left\{ x \in \{1, 2, \dots, n\} \mid \left(n \mid x^2\right) \right\} \right| = m. \]

综上：

\[|P| + |Q| = n^2 + m, \]

即：

\[\sum_{x=1}^{n} \left\lfloor \frac{x^2}{n} \right\rfloor + \left\lfloor \sqrt{nx} \right\rfloor = n^2 + \prod p_i^{\lfloor e_i / 2 \rfloor}. \]

证毕。

具体实现就是将 $n$ 质因数分解直接计算右式。

笔者赛时犯唐，用了 Pollard-Rho，复杂度约为 $\mathcal{O}(Tn^{1/4})$。

事实上可以预处理筛出 $\sqrt[3]{n}$ 即 $10^6$ 内的所有质数，剩下的是一个大于 $10^6$ 质数或两个这样质数的积，直接暴力拆开特判处理。复杂度约 $\mathcal{O}({n}^{1/3} + T(n^{2/3})^{1/2}) = \mathcal{O}(Tn^{1 / 3})$，也能过。

代码很丑就不放了。

本文通过集合证明的方式由 DeepSeek 启发，其余证明过程皆是本人书写，轻喷。