2025.9.16 模拟赛

Cycle

快速幂 构造 最大公因数 质因数分解

以下把将排列 $p$ 进行 $1$ 次 $p_i\leftarrow a_{p_i}$ 操作记为 $p\leftarrow p\times a$，那么将排列 $p$ 进行 $k$ 次 $p_i\leftarrow p_{p_i}$ 就是 $p\leftarrow 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$ 分。

#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)$ 个长度为 $\frac{c}{\gcd (c,k)}$ 的小环。

而这道题需要我们还原最开始的排列，因此是合并环。假设在给出的排列中找到了若干个长度为 $d$ 的小环，这些小环原来是长度为 $c$ 的大环，那么满足

$$\frac{c}{\gcd (c,k)}=d$$

要找出最小的 $c$ 来方便处理。然后我就不会了。

Coloring

树形dp 点分治

首先我先 $\mathcal{O}(2^n)$ 枚举出每个点的颜色，然后对于每条边染成黑色是否满足条件就可以确定下来了，因此不要实际染边的颜色。把所有满足条件的边的数量记下来，假设是 $m$，那么枚举实际染成的黑色边数量 $i$，并通过组合数计算最终答案。

$$\sum _{i=1}^m{c}^i\times \left(\genfrac{}{}{0ex}{}{m}{i}\right)$$

成功获得 $20$ 分。

Disbalance

概率与期望 组合数学 乘法逆元

• [c] 我的暴力挂了一分都没有。

大概就是每次枚举给哪个数加一，太暴力了。

---

根据讲题和 AI 分析我整理出了 $\mathcal{O}(K)$ 的解法。

• [I] 进行若干次操作之后，不同的最终状态是等概率的。不会证哈哈。

对于 $N$ 个元素，如果我们需要将 $i$ 次增量随机赋给这些元素的话，那么这就和可重组合数一样了（在 $N$ 个元素中选择 $i$ 个可重元素的组合）。根据插板法，最终状态的总数就是 $\left(\genfrac{}{}{0ex}{}{i+n-1}{i}\right)$。

由于所有最终状态等概率，因此每种状态的概率为 $\frac{1}{\left(\genfrac{}{}{0ex}{}{i+n-1}{i}\right)}$。

不平衡值的定义是对于 $m=\max a$，如果 $m>\sum a-m\iff 2m>\sum a$，那么值就为 $2m-\sum a$，否则为 $0$。

• [I] 由于元素之间地位是相等的，也没有顺序之分，因此我们可以求出其中一个数作为 $m$ 的贡献，然后将这个贡献乘以 $n$。

假设 $m$ 最终是 $a_1$，那么我们可以枚举最终给 $a_1$ 的增量 $j$，然后把剩余的 $i-j$ 个增量给到其它 $n-1$ 个元素上，方案就为

$$\underset{可重组合}{\underbrace{\left(\genfrac{}{}{0ex}{}{n-1}{i-j}\right)}}=\left(\genfrac{}{}{0ex}{}{(i-j)+(n-1)-1}{(n-1)-1}\right)=\left(\genfrac{}{}{0ex}{}{i-j+n-2}{n-2}\right)$$

再乘上每种状态的概率，对于这种情况概率就是

$$\frac{\left(\genfrac{}{}{0ex}{}{i-j+n-2}{n-2}\right)}{\left(\genfrac{}{}{0ex}{}{i+n-1}{i}\right)}$$

把枚举 $j$ 的过程显式地加入尽量，并加上对答案贡献的计算，可以得到 $f_i$ 的值

$$f_i=n\times \sum _{j=0}^i\underset{概率系数}{\underbrace{\frac{\left(\genfrac{}{}{0ex}{}{i-j+n-2}{n-2}\right)}{\left(\genfrac{}{}{0ex}{}{i+n-1}{i}\right)}}}\underset{贡献}{\underbrace{[2(j+1)-(n+i)]}}\underset{判断是否有贡献}{\underbrace{[2(j+1)>n+i]}}$$

将 $2(j+1)>n+i$ 变形得到 $j>\frac{n+i-2}{2}$，因此下界为 $\lfloor \frac{n+i-2}{2}\rfloor +1$。再把常数项移出去得到

$$f_i=\frac{n}{\left(\genfrac{}{}{0ex}{}{i+n-1}{i}\right)}\times \sum _{j=j_{\min }}^i\left(\genfrac{}{}{0ex}{}{i-j+n-2}{n-2}\right)(2j+2-n-i)$$

其中 $j_{\min }=\lfloor \frac{n+i-2}{2}\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{array}{rl}{f}_i& =\frac{n}{\left(\genfrac{}{}{0ex}{}{i+n-1}{i}\right)}\times \sum _{m=0}^{i-j_{\min }}\left(\genfrac{}{}{0ex}{}{m+n-2}{n-2}\right)(2(i-m)+2-n-i)\\ & =\frac{n}{\left(\genfrac{}{}{0ex}{}{i+n-1}{i}\right)}\times \sum _{m=0}^{i-j_{\min }}\left(\genfrac{}{}{0ex}{}{m+n-2}{n-2}\right)(i-n+2-2m)\end{array}$$

把求和拆开，就有

$$\begin{array}{rl}& =\sum _{m=0}^{i-j_{\min }}\left(\genfrac{}{}{0ex}{}{m+n-2}{n-2}\right)(i-n+2-2m)\\ & =(i-n+2)\sum _{m=0}^{i-j_{\min }}\left(\genfrac{}{}{0ex}{}{m+n-2}{n-2}\right)-2\sum _{m=0}^{i-j_{\min }}m\times \left(\genfrac{}{}{0ex}{}{m+n-2}{n-2}\right)\end{array}$$

• [!] 注意到 $n-2$ 是固定的，也就是我们所有求的组合数在杨辉三角上是同一列，而杨辉三角一列的和等于最后一个元素的右下角那个元素，也就是 ¹。对第一个求和应用恒等式得到

$$\begin{array}{rl}& =(i-n+2)\sum _{m=0}^{i-j_{\min }}\left(\genfrac{}{}{0ex}{}{m+n-2}{n-2}\right)\\ & =(i-n+2)\left(\genfrac{}{}{0ex}{}{i-j_{\min }+(n-2)+1}{(n-2)+1}\right)\\ & =(i-n+2)\left(\genfrac{}{}{0ex}{}{i-j_{\min }+n-1}{n-1}\right)\end{array}$$

对于第二个求和式，首先利用恒等式 $k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$ 的变形 $m\left(\genfrac{}{}{0ex}{}{m+a}{a}\right)=(a+1)\left(\genfrac{}{}{0ex}{}{m+a}{a+1}\right)$。若 $a=n-2$，那么 $m\left(\genfrac{}{}{0ex}{}{m+n-2}{n-2}\right)=(n-1)\left(\genfrac{}{}{0ex}{}{m+n-2}{n-1}\right)$。

所以

$$2\sum _{m=0}^{i-j_{\min }}m\times \left(\genfrac{}{}{0ex}{}{m+n-2}{n-2}\right)=2(n-1)\sum _{m=0}^{i-j_{\min }}\left(\genfrac{}{}{0ex}{}{m+n-2}{n-1}\right)$$

再次应用 $\sum _{k=M}^N\left(\genfrac{}{}{0ex}{}{k}{M}\right)=\left(\genfrac{}{}{0ex}{}{N+1}{M+1}\right)$ 恒等式，得到最终结果

$$\begin{array}{rl}& =2(n-1)\left(\genfrac{}{}{0ex}{}{(i-j_{\min }-1)+(n-1)+1}{(n-1)+1}\right)\\ & =2(n-1)\left(\genfrac{}{}{0ex}{}{i-j_{\min }+n-1}{n}\right)\end{array}$$

所以我们就得到了 $f_i$ 的最终结果

$$f_i=\frac{n}{\left(\genfrac{}{}{0ex}{}{i+n-1}{i}\right)}\left[(i-n+2)\left(\genfrac{}{}{0ex}{}{i-j_{\min }+n-1}{n-1}\right)-2(n-1)\left(\genfrac{}{}{0ex}{}{i-j_{\min }+n-1}{n}\right)\right]$$

• [!] 需要注意当 $j_{\min }>i$ 时，贡献为 $0$。

预处理阶乘和逆元后，以上公式可以 $\mathcal{O}(1)$ 进行计算。所以我们就得到了本题的 $\mathcal{O}(K)$ 解法。

Distance

树链剖分 线段树 矩阵

• [I] 以不同点为根的贡献是可以拆开进行计算的。

所以我们枚举根，然后做倍增 LCA。预处理的时候把树上前缀和的搞下来，但是这样子就无法快速子树修改了。由于 dfs 序可以做字数修改，因此按照 dfs 序把树上前缀和差分后插入到树状数组中，这样子就可以快速区间修改单点查询了。

时间复杂度 $\mathcal{O}(n^2{\log }_{2}n)$，但是常数太大只有 $10$ 分。

Footnotes

1. 朱世杰恒等式 - 维基百科，自由的百科全书 ↩