CSP2022 & NOIP2022 赛前杂题选做

2022秋 TOP

---

写在前面，大概 11.17 后都是 2200 左右 CF 题板刷+八校题/讲课题

CF1610F

Description

传送门

Solution

第一问答案很好猜。

就是相连的边权和为奇数的点，考虑如何构造。

分类讨论：

• 当 $2$ 边数量为偶数，则两两匹配最后多出一个 $1$
• 当 $2$ 边数量为奇数，则两两匹配最后多出一个 $1$ 与一个 $2$，一进一出。

奇妙的地方来了，考虑欧拉回路，把这个一进一出的东西跑出来。

新建一个虚点，向所有度数为奇的点连边，使其有欧拉回路。

跑欧拉回路时要注意，尽量跑与上一条边边权相同的边，这样可以达到把所有边匹配起来的效果。

Summary

前面基本上都想到了，就是这个欧拉回路，非常新奇。

---

[NOI Online #1 入门组] Running

Description

传送门

Solution

把题面抽象一下，求满足：$\sum_{i}{x_i} = n$ 最小表示法后不同的多元组 $x$

考虑一个 $n^2$ DP：

有两种方式，第一种是做一个完全背包，另一个是模拟赛考过的类第二类 $Striling$ 数

然后发现可以对第二维根号分治。

前一半直接背包，后一半上类第二类 $Striling$

Summary

第一道根号分值？实际上是模拟赛一道题的加强版

---

11.09 P4149 & CF600E & CF741D

Description

来自 $\text{z}\color{red}{\text{xy}}$ 的 静态树分治题单。

都是 dsu on tree，大同小异，故写在一起。

Solution

dsu on tree 用于离线解决子树询问问题，很多使用淀粉质可以解决的问题都可以用dsu on tree 解决。

具体思路是，首先将要维护的东西转化到子树中，并且当前子树的信息一般可以由儿子子树的信息合并起来得到。

这时候借用重剖的想法，取他的重儿子不删除在儿子节点维护的信息，重新遍历轻儿子，并将信息单点并入重儿子的信息内。

时间复杂度分析与重剖相似，总体 $O(n\log n)$

---

11.10 CF1005E2

Description

传送门

Solution

一个很妙的容斥。

中位数等于 $m$ 显然是个不好做的东西。

考虑容斥，转化为 $[Mid \geq m] - [Mid > m]$。

发现 $[Mid \geq m]$ 非常好做，统计一下 $\geq m$ 的数的数量，以及 $< m$ 的数量，让前者 $\geq$ 后者就好了。

Summary

很有用的容斥，感觉一般用来处理 $\geq$ 或 $\leq$ 好求但是 $=$ 不好求的情况。

---

11.10 [八校联考-11.10]foe 暴力

Description

给定 $n, a$ ，要求求出 $a^x \equiv x \pmod n$ ，并保证 $x \leq 4 * 10^{18}$

多组数据。

$1 \leq T \leq 10, 1\leq n, a \leq 10^9$

保证 $T$ 组数据中有 $90\%$ 的 $n$ 为质数，$10\%$ 的 $n$ 为合数。

Solution

观察 $n$ 为质数时的规律，通过打表等方式发现答案为 $(n - 1) * (n - 1)$

所以只要解决 $n$ 为合数的情况，不难想到拓展欧拉定理。

每次将问题缩减成：$Solve(A, n)$ to $Solve(A, \phi(n)) + \operatorname{lcm}(n, \phi(n))$

即可解决问题。

---

11.11 [八校联考-11.11]virtual 虚拟

Description

给定一个仅由 $a, b$ 组成，长度为 $n$ 的序列，若下标 $l, r$ 之间 $a$ 的数量在区间 $[lk, rk]$ 中，则给 $l, r$ 连边。

$Q$ 组询问，询问 $x, y$ 是否联通

$1 \leq n \leq 2 * 10^6, 1\leq Q \leq 2 * 10^5$

Solution

询问十分并查集，暴力连边是 $n^2$ 级的，考虑优化建图。

对于每个点 $i$，可以连边的点显然是个区间，容易发现这个区间的移动不会很大。

考虑增量分析，可以分类讨论一下。

若：$i + 1$ 区间与 $i$ 区间无交，只能暴力连边

若：$i + 1$ 区间与 $i$ 区间有交，多的部分只能暴力连边，考虑相交的部分能否优化。

显然可以直接将 $i$ 与 $i + 1$ 连边，即可处理掉相交部分。

那么这个区间可以直接双指针分析，总复杂度 $O(n\log n)$

---

11.11 [八校联考11.11] jyrg 吉滪金錀

Description

给出一个长度为 $n$ 的序列 $A$, 给出一种操作：

每次可以将 $A_i$ 变为 $A_{i + 1} - 1$，$A_{i + 1}$ 变为 $A_i + 1$，代价为 $A_i + A_{i + 1}$

要求经过若干次操作，将序列变得单调不升，问最大价值最小。

Solution

考场上想到了 [NOIP2021 T3方差]，研究了很久的前缀和与差分转化。

实际上的转化方式：我们令：$B_i = A_i - i$，那么操作变为将 $B_i$ 与 $B_{i + 1}$ 交换，代价为 $B_i + B_{i + 1} + 2i + 1$

其实和 [NOIP2021 T3方差] 思路确实差不多，都是将操作转换为序列的交换。

那么无解就很好判断了，此时相当于需要 $B_i$ 单调下降，判有无重复的 $B_i$ 即可。

有解的情况，考虑一个贪心，从前往后插入每个数，在这个数之前的序列已经被维护好了，那就是通过若干次交换使其到达正确的位置。

可以证明这样操作是最优的。

实现上，可以用平衡树维护一个区间平移以及单点插入的操作，复杂度 $O(n\log n)$

---

11.11 P4590 [TJOI2018]游园会

Description

传送门

Solution

DP 套 DP 板子题。

考虑状态 $f[i][j]$ 表示前 $i$ 位，lcs 为 $j$ 的方案。

但发现这个状态并不好转移，主要是 lcs 的信息有太多的缺失。

这种时候可以先考虑暴力补全信息，我们考虑 lcs 的求法。

令 $g[i][j]$ 表示 $A$ 串匹配了前 $i$ 位，$B$ 串匹配了前 $j$ 位的答案。

显然有

$$g[i][j] = \max{\begin{cases}g[i-1][j-1] + 1,&A_i =B_i\\ \max{(g[i-1][j],g[i][j - 1])},&A_i \neq B_i\\ \end{cases}}$$

暴力的将 $g$ 数组全部压进状态里，则 lcs 的限制可以解决，但需要优化。

首先来挖掘 $g$ 数组DP的一些性质。

• 1. $g[i]$ 的转移只跟 $g[i - 1]$ 与 $A_i$ 有关，所以可以只记录一行的状态
• 1. 从 $g[i][j - 1]$ 到 $g[i][j]$ 最多增加 $1$，所以其差分数组可以二进制状压。

那么我们就得出了优化的方式，直接状压其差分数组，这样状态可以缩减到 $O(2^k)$

最后再加上不能有连续 NOI 的限制，记一个 $k = \{0,1,2\}$ 表示已经有连续的几位了，分讨转移即可。

所以最后的状态：$f[i][State][k]$ 复杂度大概是 $O(n\times 2^k)$ 级别的。

然而这个东西还有一种理解方式：

如果熟悉自动机算法的同学，可以发现 $g$ 数组实际上充当了一个类似自动机的作用。

即从一个 $State$ 经过 $c$ 字符这条边，可以到另一个 $New\_State$，$f$ 数组就是按这个顺序，也就是在 $g$ 这个自动机上转移的。

所以 DP 套 DP 实际上是利用一个DP构建一个较复杂的自动机，再在这个自动机上将问题解决。

实际实现时可以不用直接把自动机构造出来，而是边转移时边把 $g$ 数组递推，得到接下来的可能状态。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxK = 15, maxn = 1005, mod = 1e9 + 7;
int n, K, op;
char S[maxK + 5];
int f[2][1 << maxK][3], POPCnt[1 << maxK], num[2][maxn], Answer[maxK + 5];
inline int Hash(int State, char c) {
    for(register int i = 1; i <= K; ++i) num[0][i] = (State >> (i - 1)) & 1, num[0][i] += num[0][i - 1];
    for(register int i = 1; i <= K; ++i) num[1][i] = max(num[1][i - 1], max(num[0][i], num[0][i - 1] + (S[i] == c)));
    int New_State = 0;
    for(register int i = 1; i <= K; ++i) New_State |= (num[1][i] - num[1][i - 1]) << (i - 1);
    return New_State;
}
signed main() {
//    freopen("P4590.in", "r", stdin);
//    freopen("P4590.out", "w", stdout);
    n = read(), K = read();
    scanf("%s", S + 1);
    for(register int i = 1; i < (1ll << K); ++i) POPCnt[i] = POPCnt[i >> 1] + (i & 1);
    f[0][0][0] = 1;
    for(register int i = 1; i <= n; ++i) {
        op ^= 1; int State;
        for(register int j = 0; j < (1ll << K); ++j) 
            for(register int k = 0; k < 3; ++k) f[op][j][k] = 0;
        for(register int j = 0; j < (1ll << K); ++j) {
            if(f[op ^ 1][j][0]) {
                State = Hash(j, 'N'), f[op][State][1] = (f[op][State][1] + f[op ^ 1][j][0]) % mod;
                State = Hash(j, 'O'), f[op][State][0] = (f[op][State][0] + f[op ^ 1][j][0]) % mod;
                State = Hash(j, 'I'), f[op][State][0] = (f[op][State][0] + f[op ^ 1][j][0]) % mod;
            }
            if(f[op ^ 1][j][1]) {
                State = Hash(j, 'N'), f[op][State][1] = (f[op][State][1] + f[op ^ 1][j][1]) % mod;
                State = Hash(j, 'O'), f[op][State][2] = (f[op][State][2] + f[op ^ 1][j][1]) % mod;
                State = Hash(j, 'I'), f[op][State][0] = (f[op][State][0] + f[op ^ 1][j][1]) % mod;
            }
            if(f[op ^ 1][j][2]) {
                State = Hash(j, 'N'), f[op][State][1] = (f[op][State][1] + f[op ^ 1][j][2]) % mod;
                State = Hash(j, 'O'), f[op][State][0] = (f[op][State][0] + f[op ^ 1][j][2]) % mod;
            } 
        }
    }
    for(register int i = 0; i < (1ll << K); ++i) Answer[POPCnt[i]] = (Answer[POPCnt[i]] + (f[op][i][0] + f[op][i][1] + f[op][i][2]) % mod) % mod;
    for(register int i = 0; i <= K; ++i) printf("%lld\n", Answer[i]);
    return 0;
}

---

11.12 CF1720D1

Description

传送门

Solution

考虑暴力DP，设 $f[i]$ 为前 $i$ 位的答案。

显然有 $f[i] = \max_{a_i \oplus j < a_j \oplus i}{f[j] + 1}$

显然只能优化转移，考虑这个比较难处理的条件有什么性质：

首先要知道一个结论：$a - b \leq a \oplus b \leq a + b$

于是有：$a_i - j \leq a_i \oplus j < a_j \oplus i \leq a_j + i$

有：$i - j < a_i + a_j \leq 400$

所以对于 $f[i]$ 最多只有 $400$ 个 $f[j]$ 对他有贡献，复杂度优化至 $O(maxw\times n)$

---

11.13 CSP2022-S 订正

Solution

传送门

11.15 格路计数-翻折法 P1641 & ABC205E

Description

传送门1

传送门2

Solution

一类格路计数问题。

首先要了解到，从 $(0, 0)$ 开始 向右向上走到 $(n, m)$ 的方案数是 $\dbinom{n + m}{n}$，这是最基本的格路计数

现在我们给格路加上一条 $y = x + k$ 的障碍。

我们想知道不经过这条直线的方案数。

考虑容斥。

我们考虑经过这条直线的路径形态，他一定由一段直线下的与一段直线上的路径组成。

我们把在直线下的路径翻折到直线上，会发现所有的不合法路径对应着 从 $(0,0)$ 关于 $y = x + k$ 的对称点开始的所有方案。

所以原问题答案就是：$\dbinom{n+m}{n} - \dbinom{n+m}{m+k+1}$

---

11.16 CF1715E

Description

传送门

Solution

容易考虑到分层图最短路，瓶颈在于每层之间的边数有 $n^2$ 条。

考虑优化这部分的建图。

研究一下那个特殊边权的性质：

$$f_{u} = \min_{v = 1}^n {f_v + (u - v)^2}$$

拆一下式子再把只跟 $i$ 有关的移下项：

$$f_{u} - u^2 = \min_{v = 1}^n{f_v + v^2 - 2uv}$$

一个很明显的斜率优化形式，$b = f_{u} - u^2$，$y = f_v + v^2$，$k = -2u$，$x = v$

所以在层与层之间我们可以使用斜率优化 DP 来转移，这样复杂度可以优化到 $O(n\log n)$。

每次就先用 Dij 跑出当前层的答案，然后跑一边DP 跑出下一层的初始状态。

总复杂度 $O(kn \log n)$

Summary

提示我们在分层图或者其他最短路结构中，对于某些特殊的边权或者转移，可以单独拎出来用其他方式转移，将 Dij 分阶段进行，是很好的思路。

---

11.16 [八校联考] so

Description

小 L 喜欢数列和矩阵。现在他有一个长度为 $n$ 的序列 $a$。

在 $m$ 天的时间内，小 L 在第 $i$ 天会选择一个他喜欢的权值 $k_i$，并把这些数排成一个列数为 $k_i$ 的矩阵。具体地，小 L 会将 $a_x$ 排在矩阵的 $\left\lceil\dfrac{x-1}{k_i}\right\rceil+1$ 行。你可能会发现矩阵的最后一行缺了一些数，但是他并不关心这个。将数列排成矩阵之后，小 L 会对所有 $r\in\left[1,\left\lceil\dfrac{n}{k_i}\right\rceil\right]$ 计算第 $r$ 行的和，并将其记作 $s_{i,r}$。

$m$ 天之后小 L 把数列弄丢了，他只记得所有 $s_{i,r}$ 的值。小 L 想知道通过他所知的信息，最多能找回数列中的几个值。小 L 知道你是聪明绝顶的 OIer，所以他只会告诉你 $k_i$ 的值，你能回答出他的问题吗？

$n \leq 10^{12}$, $m \leq 14$

Solution

YL场的T3，做了本题的验题人，数据没有出锅，且被 yekai 妙评（

把题意简化一下，它相当于给出了很多组 被 $k_i$ 整除的位置的前缀和。

考虑确定 $i$ 的条件，当且仅当：存在 $k_{j1} \mid i$，$k_{j2} \mid i - 1$

考虑计数这个东西，那么有：$a \times k_{j1} - b \times k_{j2} = 1$

Exgcd 求一定范围内解的数量即可，但显然会有重，那么难点来到去重。

设：$f(S,T)$ 表示 $k_{j1} \mid i \Leftrightarrow j_1 \in S$, $k_{j2} \mid i - 1\Leftrightarrow j_2 \in T$ 的方案数

注意 $\Leftrightarrow$ 与 $\Rightarrow$ 的区别，前者表示恰好，已经被去重，后者表示满足，需要去重。

那么答案就是 $\sum_{S \neq \varnothing, T \neq \varnothing}{f(S,T)}$

然后我们上子集反演。

设：$A(S,T)$ 表示 $k_{j1} \mid i \Rightarrow j_1 \in S$，$k_{j2} \mid i - 1 \Rightarrow j_2 \in T$ 的方案数。

这个式子的答案非常好求，我们考虑 $k_{j1} \mid i, k_{j1} \in S$ 成立，相当于 $\operatorname{lcm}(k_j)_{k_j \in S} \mid i$ 第二个条件同理。

转化为 $\operatorname{lcm}$ 后可以套用前面的 Exgcd 求解。

子集反演一下：

为了辅助推导：我们设 $g(S,T)$ 表示 $k_{j1} \mid i \Leftrightarrow j_1 \in S$，$k_{j2} \mid i \rightarrow j_2 \in T$ 的方案

则有：

$$g(S,T) = \sum_{V \subseteq T}{f(S,V)}$$

反演过来就是：

$$f(S,T) = \sum_{V \subseteq T}{(-1)^{|V|-|T|}g(S,V)}$$

又有：

$$f(S,T) = g(S, \varnothing) - f(S, \varnothing)$$

所以有：

$$\sum_{T \neq \varnothing}f(S,T) = \sum_{T \neq \varnothing}{(-1)^{|T|-1}{g(S,T)}}$$

同理对 $g(S,T)$ 和 $A(S,T)$ 反演，有：

$$\sum_{S \neq \varnothing}g(S, T) = \sum_{S \neq \varnothing}{(-1)^{|S| - 1}{A(S,T)}}$$

推出答案式子：

$$\sum_{S \neq \varnothing, T \neq \varnothing} f(S,T) = \sum_{S \neq \varnothing}\sum_{T \neq \varnothing}{(-1)^{|T| - 1}g(S,T)}$$

交换求和顺序后可以将 $g(S,T)$ 的反演式表示，得出最后的式子：

$$\sum_{S \neq \varnothing, T \neq \varnothing} f(S,T) = \sum_{S \neq \varnothing, T \neq \varnothing}{(-1)^{|S|+|T|}A(S,T)}$$

此时这个式子已经可以以 $4^{m}$ 的复杂度解决此题了。

但在 $m = 14$ 时这个复杂度似乎还是不太可以接受，我们考虑能否再降一些。

发现如果 $k_j \mid i$ 且 $k_j \mid i + 1$ 显然有 $k_j = 1$，若单独处理，则可以保证 $S \bigcap T = \varnothing$

枚举子集的复杂度降至 $3^{m}$ 可以通过此题。

---

11.17 [2200 Trees] CF980E

Description

传送门

Solution

首先写在前面一个未知错误性的错误做法。

以一个度数大于 $1$ 的点为根，开个堆维护，每次删除最小的叶子，并将新生成的叶子加入堆。

听说是错的，但是并没 hack 出来，咕了。

正解如下：

首先套路的把删 $K$ 个点变为保留 $n - K$ 个点的连通块，并获得他们的贡献。

显然贡献很特殊，$2^i$ 算一种经典贡献，可以直接贪心的从大往小选一定最优。

那么问题变为 check 每个点能否被选。

假设现在已经选出的点的集合为 $S$，那么当前点 $x$ 能被选入，当且仅当：$x$ 到 $S$ 的最短距离 $\leq n - K - |S|$，原因是在这条路径上的点都要被加入集合中。

这个问题看似不好维护，但我们发现 $n$ 一定可以被选入集合中。

所以可以将 $n$ 作为根，那么很容易发现 $x$ 到 $S$ 的最短路径一定在 $x$ 到根的路径上。

那么就很好维护了，倍增或树剖均可。

---

11.17 [2200 Trees] CF76A

Description

传送门

Solution

他相当于是求一个类似带两个权值的最小瓶颈生成树

容易考虑先对一个权值把最小生成树拉出来。

然后我们想要增大 $s_i$ 那部分的权值，降低 $t_i$ 那部分的权值。

这个过程相当于是把不在生成树上的每条边依次尝试换上去。

每次换一条边，就对于那颗基环树重新跑一边MST

然后稍微玩一下发现这个东西显然有单调性，双指针即可。

---

11.17 [2200 Trees] CF575B

Description

传送门

Solution

一眼想了个树剖的两 $\log$ 做法，然后看题解发现有单 $\log$ 的写法

发现自己居然没有想到树上差分，这个东西相当于是静态树上路径修改+查询，确实很适合用树上差分。

需要注意的是，$x \to lca$ 与 $lca \to y$ 显然是不同的，所以你要分开差分，令一个是 $Up$，一个是 $Down$

分开统计一下就好了

---

11.17 [2300 Graphs] CF662B

Description

传送门

Solution

一开始瞎猜了个什么二分图判定，想了一会发现和二分图好像一点关系都没有。

显然变成全红与全蓝是类似的问题，我们只考虑全红。

对于一条边，只有翻转他的左右端点的时候才会将它翻转。

那么对于一条红边，要么同时翻转左右端点，要么都不翻转。

对于一条蓝边，只能翻转一边的端点。

这是个十分 2-SAT 的结构，2-SAT 判断之后方案构造优先选 $1$ 更少的集合就行了。

但是还未结束，发现这题的图是个无向边，那么不需要判断强联通，而是直接判连通块，可以用并查集代替 Tarjan。

---

11.18 [2100 DP] CF1271D

Description

传送门

Solution

事实证明，完全不会 DP，做不出来 2100 DP 的概率大于 做不出来 2300 左右 Tree/Graph 的概率

进入正题。

考虑一个贪心的结论，由于驻守的代价均为 $1$，所以尽量把驻守的时间往后拖一定不劣。

设 $f[i][j]$ 表示 当前打到了 $i$ 的城堡，还剩下 $j$ 个士兵，随便判一下转移一下即可。

这能没做出来？？？

11.18 [2200 Trees] CF77C

Description

传送门

Solution

猜个结论，考虑走到一个点后，一定会把子树的贡献拿满，然后不再走回这颗子树。

想了一会觉得挺有道理，也就是在 $x$ 点时，选取子树答案前 $a_x$ 大的子树走。

但是 $a_x$ 大于儿子数时会有小问题，我们发现剩余的 $a_x$ 与 儿子剩余的 $a_y$ 可以来回走，达到不浪费的效果。

稍微修正一下，记录子树根节点剩余权值，与根节点匹配一下即可。

11.18 [2100 Maths] CF1748D

Description

传送门

Solution

构造是真难。 /sad

让两个东西同时成立比较困难，我们考虑让 $a \operatorname{or} x = b \operatorname{or} x$，这是很容易做到的，这样我们就只需要考虑构造 $d \mid (a \operatorname{or} x)$

进一步地，我们拆分这个条件为： $x$ 完全包含 $a$ 的所有 $1$ 位 且 $d \mid x$

然后有很多构造方式，下面选取其中最妙的一种：

我们优先满足 $d | x$ 的条件，让 $x$ 由若干个 $d$ 相加得到。

然后考虑每次将 $d * 2^k$ 将它加到 $x$ 上，让 $d * 2^k$ 的 $lowbit$ 刚好加到 $x$ 当前位为 $0$ 但 $a$ 当前位为 $1$ 的位置上。

容易发现这种构造方式不会影响已经构造好的位，并且 $x \leq 2^{60}$

11.18 [2400 Trees] CF1051F

Description

传送门

Solution

一道难度虚高的题目。

我们注意到 $m - n \leq 20$ ，显然是解题的关键。

这个条件意味着原图可看成树加上几条边，容易想到先拉一颗生成树出来。

考虑 $u$ 到 $v$ 的最短路径，分类讨论。

若 $u$ 到 $v$ 的最短路径都在树上，显然可以直接 LCA 求距离。

若 $u$ 到 $v$ 的最短路径经过了非树边

这里容易进入的误区是考虑将每一条边替换上去，非常不好做。

实际上由于最多只有 $20$ 条非树边，所以最多只有 $40$ 个端点。

我们对这 $40$ 个端点都跑一边单源最短路。

那么这一部分的情况就形如：$\min{(Dis(x,k) + Dis(k, y))}$

两者取最小，问题得到解决。

11.19 [八校联考] course 选课

Description

传送门(私)

Solution

事实证明我完全不会网络流。。。

赛时 70pts 的二分图匹配都挂了，亏麻了。

建图好像不是最优的，但是实在想不懂最优的建图怎么用霍尔定理证正确性。

就放个觉得正确性很对的三分图做法。

显然二分答案 $x$ ，然后 $S$ 连向每个人，容量为 $C$，每个人连向每节课，容量为 $1$，每节课 连向每个时间点，容量为 $a[i][j]$，每个时间点连向 $T$，容量为 $x$

判断是否满流即可，至于证明，我们有种精妙的构造（bushi

---

11.19 [八校联考] tree 生成树

Description

传送门(私)

Solution

神仙题。

考虑类似点分治的过程。

每次找个点分中心，然后将它删掉，划分成多个子连通块，令一个与点分中心相连的点为“根”，那么把 “根” 与点分中心的边取出，重复此过程，删点的路径会构成一颗树。

然后考虑一个重要转化：$\sum{dep(x)} = \sum{Siz(x)}$

其中 $Siz(x)$ 代表子树大小。

然后做一个集合 DP 即可。

11.20 [2100 DP] CF980D

Description

传送门

Solution

首先要猜出一个结论：

若：$a \times b = p^2, a \times c = q^2$ 则有：$b \times c = r^2$

证明可以考虑把 $a,b,c$ 分别分解，考虑指数。

过程很简单，不放了。

也就是说这东西具有传递性，那么只要在同一个连通块内的东西都可以在一个组。

那么 $(l, r)$ 可行，等同于为 $(l, r - 1)$，且 $r$ 的连通块出现过。

预处理一下并查集，暴力算每个区间的答案即可。

11.20 [八校联考] perm 排列

Description

传送门(私)

Solution

题目的限制相当于要求 前 $A$ 个数 两两不在同一置换环中，后 $B$ 个数同理。

我们考虑部分分。

$1^o$ 当：$A + B > n$

中间相交的段只能连自环，而两边的点要么连成自环，要么剩余 $A$ 中的某点找剩余 $B$ 中的某点匹配，连成二元环。

枚举匹配的数量，很容易计数（下面假设 $n - B \geq n - A$，否则 swap）：

$$Ans = \sum_{i = 1}^{B}{\dbinom{n - B}{i}\dbinom{n - A}{i}}i!$$

$2^o$ 当：$B = 0$

我们称没有限制的段为 $C$ 段。

我们可以先将 $A$ 段的每个点都设成自环，然后考虑将 $C$ 段的点以此插入其中。

由于是圆排，所以相当于第 $i$ 次插入有 $A+i-1$ 个位置可以插，这样可以做到不重不漏，那么答案就是一个下降幂：

$$Ans = n^{\underline{n-A}} = \frac{n!}{A!}$$

也可以用第一类 $\text{Stiriling}$ 数推

$3^o$ 当：$A + B \leq n$

我们尝试用 $A + B > n$ 与 $B = 0$ 的情况来推出 $A + B \leq n$ 的情况。

我们先在 $A, B$ 中各挑出 $i$ 个数匹配成二元环，接下来就是 $B = 0$ 时的将中间的 $C$ 插入进每个自环与二元环中的过程。

上式的 $A$ 要变成 $A + B$，所以答案就是（依然假设 $A \geq B$）：

$$Ans = \frac{n!}{(A +B)!}\sum_{i = 1}^{B}{\dbinom{n - B}{i}\dbinom{n - A}{i}}i!$$

此题结束。

---

11.20 [2400 & 2900 Others] CF802N & CF802O

Description

传送门

传送门

Solution

对于 $\text{Middle}$ ，给出费用流做法。

首先暴力的建个图。

$S$ 连每个 $i$，容量为 $1$，费用为 $a_i$，每个 $i$ 连 $j$ ($i < j$) 每个 $i$ 连 $T$，容量为 $1$，费用 $b_i$，$T$ 连 $T'$ 流量为 $k$

但是这样跑不过，我们考虑去掉一些无用的边。

来自 $\color{black}{\text{G}}\color{red}{\text{raphcity}}$ 的最优建图：

我们建一张一分图，从 $S$ 连每个 $i$，容量为 $1$ 费用 $a_i$，从每个 $i$ 连 $T$ 容量 $1$ 费用 $b_i$，每个 $i$ 连 $i + 1$ 容量 $\infty$ 费用 $0$，最后 $T$ 连 $T'$

可以跑过，事实证明我还是不会网络流 \sad

对于 $\text{Hard}$ ，给出 $\text{wqs}$ 二分加反悔贪心做法。

因为它是个费用流模型，所以每次增广单调不降，也就是说答案是个凸函数，又要求恰好分 $k$ 段。

考虑 $\text{wqs}$ 二分。

那么现在我们不对选的数量做要求，但是每次选要 $-mid$ 的贡献。

然后我们考虑一个足够简单的贪心。

对于每个 $b_i$ 我们找到最小的未被匹配的 $a_j$ 将他们匹配。

这个贪心显然是错的，但这很像一个二分图匹配的过程，考虑反悔。

我们发现将 $(a_i,b_j)$ 的匹配换成 $(a_i,b_k)$ 的匹配，贡献相差了：

$$(a_i+b_k-s) - (a_i+b_j-s)=b_j + (-b_k)$$

而选取一个匹配的贡献是：$b_j+(a_i-s)$

所以我们把 $a_i - s$ 一次性丢入堆中，每次取出来时再把 $-b_i$ 丢回去作为反悔选项即可。

注意：反悔的选择不能累计到分段的段数中。

---

11.21 P4072 征途

Description

传送门

Solution

看到方差，考虑方差的经典求法：$(\sum_{i}^{m}{v_i})^2 - m \times \sum_{i}^{m}{v_i^2}$

先考虑个 $O(n^2\log n)$ 的做法。

设：$f[i][j]$ 表示前 $i$ 天，划分为 $j$ 段的答案。

发现可以斜率优化，此时已经可以 $O(n^2\log n)$ 通过此题。

然后发现这个 划分为 $j$ 段很烦，他并不在斜优的优化里。

可以斜优，又要强制 $k$ 段，考虑 $\text{wqs}$ 二分。

用 斜优的 $\text{DP}$ $\text{check}$ ，做到 $O(n\log n)$

11.21 [2000 maths] CF900D

Description

传送门

Solution

首先显然需要有 $y \mid x$，否则 $0$

那么把 $x$ 除掉 $y$，则要统计和为 $x$ 且互相互质的 $n$ 元组

我们考虑那个和的限制，我们枚举 $n$，然后插板，发现答案可以化简。

那么设 $g(x)$ 表示和为 $x$ 的答案，则 $g(x) = 2^{x - 1}$

然后把互质的条件加上，令 $f(x)$ 为满足互质的答案，不难发现：

$$g(x) = \sum_{d \mid x}{f(d)}$$

接下来有两种做法。

$1^o$ 莫反

直接套莫反结论：

$$f(x) = \sum_{d\mid x}\mu(\frac{x}{d})g(d)$$

暴力求解这个式子，复杂度 $O(\frac{m}{\log m})$

$2^o$ 经典 $\gcd$ 容斥

用一种很经典的 $\gcd$ 容斥方法：

$$f(x) = g(x) - \sum_{d \mid x, d>1}{f(\frac{x}{d})}$$

也是暴力求解即可，复杂度 $O(\operatorname{d}(m)\sqrt{m}\log m)$