2025.9.16 模拟赛 - 渴鹅笔记 Haokee Note

## Cycle 以下把将排列 $p$ 进行 $1$ 次 $p_i\gets a_{p_i}$ 操作记为 $p\gets p\times a$，那么将排列 $p$ 进行 $k$ 次 $p_i\gets p_{p_i}$ 就是 $p\gets p^k$。 - [I] 首先我想到了一个思路：求出答案的逆排列 $p^{-1}$，然后计算 $p_k\times \left(p_{-1}\right)^k$ 是否为 $a:a_i=i$。但是我肯定是求不出答案的逆排列的，所以这个做法写不了。然后我会了 $n\le 10,k\le 2\times 10^5$ 的做法。首先一个 $\mathcal O(n!)$ 的搜排列是很简单的，但是判断是否合法需要点功夫。我发现我定义的乘方运算满足结合律，因此可以进行排列快速幂。时间复杂度 $\mathcal O(n!\times n\log_2 k)$，可以通过 $25$ 分。 ```cpp #include <iostream> #include <numeric> using namespace std; const int kMaxN = 1e5 + 5; int a[kMaxN], b[kMaxN], f[kMaxN], res[kMaxN], tmp[kMaxN], ans[kMaxN], c[kMaxN], n, k, has; void times(int res[], int other[]) { copy(other + 1, other + n + 1, tmp + 1); for (int i = 1; i <= n; i++) { res[i] = tmp[res[i]]; } } void pow(int k) { copy(a + 1, a + n + 1, b + 1); iota(res + 1, res + n + 1, 1); for (; k; k /= 2) { if (k % 2) { times(res, b); } times(b, b); } } bool check() { pow(k); return equal(res + 1, res + n + 1, ans + 1); } void dfs(int x) { if (has) { return; } if (x > n) { if (check()) { has = 1; copy(a + 1, a + n + 1, c + 1); } return; } for (int i = 1; i <= n; i++) { if (f[i]) { continue; } f[i] = 1; a[x] = i; dfs(x + 1); f[i] = 0; } } int main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> k; for (int i = 1; i <= n; i++) { cin >> ans[i]; } dfs(1); for (int i = 1; i <= n; i++) { cout << c[i] << ' '; } return 0; } ``` 接下来我就思考排列的性质。一个排列可以拆成若干个不相干的环（$i$ 往 $p_i$ 连边），而我发现将排列进行 $k$ 次方运算之后，原排列中一个长度为 $c$ 的环会变成 $\gcd(c,k)$ 个长度为 $\cfrac{c}{\gcd(c,k)}$ 的小环。而这道题需要我们还原最开始的排列，因此是合并环。假设在给出的排列中找到了若干个长度为 $d$ 的小环，这些小环原来是长度为 $c$ 的大环，那么满足 $ \cfrac{c}{\gcd(c,k)}=d $ 要找出最小的 $c$ 来方便处理。然后我就不会了。 ## Coloring 首先我先 $\mathcal O(2^n)$ 枚举出每个点的颜色，然后对于每条边染成黑色是否满足条件就可以确定下来了，因此不要实际染边的颜色。把所有满足条件的边的数量记下来，假设是 $m$，那么枚举实际染成的黑色边数量 $i$，并通过组合数计算最终答案。 $ \sum_{i=1}^m c^i\times\binom{m}{i} $ 成功获得 $20$ 分。 ## Disbalance - [c] 我的暴力挂了一分都没有。大概就是每次枚举给哪个数加一，太暴力了。 --- 根据讲题和 AI 分析我整理出了 $\mathcal O(K)$ 的解法。 - [I] 进行若干次操作之后，不同的最终状态是等概率的。不会证哈哈。对于 $N$ 个元素，如果我们需要将 $i$ 次增量随机赋给这些元素的话，那么这就和可重组合数一样了（在 $N$ 个元素中选择 $i$ 个可重元素的组合）。根据插板法，最终状态的总数就是 $\dbinom{i+n-1}{i}$。由于所有最终状态等概率，因此每种状态的概率为 $\cfrac{1}{\binom{i+n-1}{i}}$。不平衡值的定义是对于 $m=\max a$，如果 $m>\sum a-m\Leftrightarrow 2m>\sum a$，那么值就为 $2m-\sum a$，否则为 $0$。 - [I] 由于元素之间地位是相等的，也没有顺序之分，因此我们可以求出其中一个数作为 $m$ 的贡献，然后将这个贡献乘以 $n$。假设 $m$ 最终是 $a_1$，那么我们可以枚举最终给 $a_1$ 的增量 $j$，然后把剩余的 $i-j$ 个增量给到其它 $n-1$ 个元素上，方案就为 $ \underbrace{\binom{n-1}{i-j}}_{可重组合}=\binom{(i-j)+(n-1)-1}{(n-1)-1}=\binom{i-j+n-2}{n-2} $ 再乘上每种状态的概率，对于这种情况概率就是 $ \cfrac{\binom{i-j+n-2}{n-2}}{\binom{i+n-1}{i}} $ 把枚举 $j$ 的过程显式地加入尽量，并加上对答案贡献的计算，可以得到 $f_i$ 的值 $ f_i=n\times\sum_{j=0}^i\underbrace{\cfrac{\binom{i-j+n-2}{n-2}}{\binom{i+n-1}{i}}}_{概率系数}\underbrace{[2(j+1)-(n+i)]}_{贡献}\underbrace{[2(j+1)>n+i]}_{判断是否有贡献} $ 将 $2(j+1)>n+i$ 变形得到 $j>\cfrac{n+i-2}{2}$，因此下界为 $\left\lfloor\cfrac{n+i-2}{2}\right\rfloor+1$。再把常数项移出去得到 $ f_i=\cfrac{n}{\binom{i+n-1}{i}}\times\sum_{j=j_{\min}}^i\binom{i-j+n-2}{n-2}(2j+2-n-i) $ 其中 $j_{\min}=\left\lfloor\cfrac{n+i-2}{2}\right\rfloor+1$。直接暴力计算时间复杂度 $\mathcal O(K^2)$，需要化简求和部分。 - [n] 先进行换元，令 $m=i-j$，那么 $j=i-m$，由于 $j\in [j_{\min},n]$，所以 $m\in [i-j_{\min},0]$。带入原式得到 $ \begin{aligned} f_i&=\cfrac{n}{\binom{i+n-1}{i}}\times\sum_{m=0}^{i-j_{\min}}\binom{m+n-2}{n-2}(2(i-m)+2-n-i) \\ &=\cfrac{n}{\binom{i+n-1}{i}}\times\sum_{m=0}^{i-j_{\min}}\binom{m+n-2}{n-2}(i-n+2-2m) \end{aligned} $ 把求和拆开，就有 $ \begin{aligned} &\textcolor{white}{=}\sum_{m=0}^{i-j_{\min}}\binom{m+n-2}{n-2}(i-n+2-2m)\\ &=(i-n+2)\sum_{m=0}^{i-j_{\min}}\binom{m+n-2}{n-2}-2\sum_{m=0}^{i-j_{\min}}m\times\binom{m+n-2}{n-2} \end{aligned} $ - [!] 注意到 $n-2$ 是固定的，也就是我们所有求的组合数在杨辉三角上是同一列，而杨辉三角一列的和等于最后一个元素的右下角那个元素，也就是 [^1]。对第一个求和应用恒等式得到 $ \begin{aligned} &\textcolor{white}{=}(i-n+2)\sum_{m=0}^{i-j_{\min}}\binom{m+n-2}{n-2} \\ &=(i-n+2)\binom{i-j_{\min}+(n-2)+1}{(n-2)+1} \\ &=(i-n+2)\binom{i-j_{\min}+n-1}{n-1} \end{aligned} $ 对于第二个求和式，首先利用恒等式 $k\dbinom{n}{k}=n\dbinom{n-1}{k-1}$ 的变形 $m\dbinom{m+a}{a}=(a+1)\dbinom{m+a}{a+1}$。若 $a=n-2$，那么 $m\dbinom{m+n-2}{n-2}=(n-1)\dbinom{m+n-2}{n-1}$。所以 $ 2\sum_{m=0}^{i-j_{\min}}m\times\binom{m+n-2}{n-2}=2(n-1)\sum_{m=0}^{i-j_{\min}}\binom{m+n-2}{n-1} $ 再次应用 $\sum\limits_{k=M}^N\dbinom{k}{M}=\dbinom{N+1}{M+1}$ 恒等式，得到最终结果 $ \begin{aligned} &=2(n-1)\binom{(i-j_{\min}-1)+(n-1)+1}{(n-1)+1} \\ &=2(n-1)\binom{i-j_{\min}+n-1}{n} \end{aligned} $ 所以我们就得到了 $f_i$ 的最终结果 $ f_i=\cfrac{n}{\binom{i+n-1}{i}}\times\left[(i-n+2)\binom{i-j_{\min}+n-1}{n-1}-2(n-1)\binom{i-j_{\min}+n-1}{n}\right] $ - [!] 需要注意当 $j_{\min}>i$ 时，贡献为 $0$。预处理阶乘和逆元后，以上公式可以 $\mathcal O(1)$ 进行计算。所以我们就得到了本题的 $\mathcal O(K)$ 解法。注意计算 $\dbinom{i+n-1}{i}$ 的逆的时候不要算完再求逆，直接用阶乘和阶乘逆拼出来就行了。 ```cpp #include <iostream> using namespace std; using LL = long long; const LL kMaxN = 4e6 + 5, kMod = 998244353; LL f[kMaxN], inv[kMaxN], t, n, k; LL pow(LL a, LL b) { LL res = 1; for (; b; b /= 2) { b % 2 && (res = res * a % kMod); a = a * a % kMod; } return res; } void init() { f[0] = inv[0] = 1; for (LL i = 1; i < kMaxN; i++) { inv[i] = pow(f[i] = f[i - 1] * i % kMod, kMod - 2); } } LL binom(LL n, LL m) { if (m > n) { return 0; } return f[n] * inv[n - m] % kMod * inv[m] % kMod; } int main() { cin.tie(0)->sync_with_stdio(0); init(); for (cin >> t; t; t--) { cin >> n >> k; LL ans = 0; for (LL i = 1; i <= k; i++) { LL jmin = (n + i - 2) / 2 + 1; if (jmin <= i) { LL a = i - jmin + n - 1; int x = ((i - n + 2) * binom(a, n - 1) % kMod - 2 * (n - 1) % kMod * binom(a, n) % kMod + kMod) % kMod * inv[i + n - 1] % kMod * f[i] % kMod * f[n - 1] % kMod * n % kMod; ans ^= i * x; } } cout << ans << '\n'; } return 0; } ``` [^1]: [朱世杰恒等式 - 维基百科，自由的百科全书](https://zh.wikipedia.org/wiki/%E6%9C%B1%E4%B8%96%E6%9D%B0%E6%81%92%E7%AD%89%E5%BC%8F) ## Distance - [I] 以不同点为根的贡献是可以拆开进行计算的。所以我们枚举根，然后做倍增 LCA。预处理的时候把树上前缀和的搞下来，但是这样子就无法快速子树修改了。由于 dfs 序可以做字数修改，因此按照 dfs 序把树上前缀和差分后插入到树状数组中，这样子就可以快速区间修改单点查询了。时间复杂度 $\mathcal O(n^2\log_2 n)$，但是常数太大只有 $10$ 分。