2025.11.13 模拟赛

种树

数学 质因数分解 贪心

首先看到乘积、因数这类的，就很难不想到做质因数分解。对于一个正整数 $n$，如果它的唯一质因数分解为 $n=\prod a^k$（$k$ 是质因子 $a$ 在 $n$ 中的出现次数），那么它的因数个数 $\text{d}(n)=\prod (k+1)$。直观来看就是每个质因数都有 $k+1$ 种取指数的方式。

现在考虑 $w$ 分过来对 $\prod \text{d}(a_i)$ 的影响。分质因子考虑，枚举质因子，假设其在 $w$ 中的出现次数为 $t$，在 $a_i$ 中的出现次数为 $k_i$，那么相当于你可以对任意 $k_i$ 进行 $t$ 次 $+1$ 操作（分一个质因子过去）。

显然，要最大化 $\prod (k_i+1)$，每次你就把最小的 $k_i\leftarrow k_i+1$ 即可。最终这个质因子对答案的贡献就是 $\prod (k_i+1)$。把所有质因子的贡献都乘起来即可。时间复杂度 $\mathcal{O}\left(n\sqrt{V}\right)$。

const LL kMaxN = 1e4 + 5, kMod = 998244353;
 
LL a[kMaxN], n, w, ans = 1;
priority_queue<LL, vector<LL>, greater<>> q;
 
void solve(LL x, LL k) {
  for (LL i = 1; i <= n; i++) {
    LL cnt = 0;
    for (; a[i] % x == 0; a[i] /= x) {
      cnt++;
    }
    q.push(cnt + 1);
  }
  while (k--) {
    LL x = q.top();
    q.pop();
    q.push(x + 1);
  }
  for (; q.size(); q.pop()) {
    ans = ans * q.top() % kMod;
  }
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> w;
  for (LL i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (LL i = 2; i * i <= w; i++) {
    if (w % i) {
      continue;
    }
    LL cnt = 0;
    for (; w % i == 0; w /= i) {
      cnt++;
    }
    solve(i, cnt);
  }
  if (w > 1) {
    solve(w, 1);
  }
  for (LL i = 1; i <= n; i++) {
    for (LL j = 2; j * j <= a[i]; j++) {
      if (a[i] % j) {
        continue;
      }
      LL cnt = 0;
      for (; a[i] % j == 0; a[i] /= j) {
        cnt++;
      }
      ans = ans * (cnt + 1) % kMod;
    }
    if (a[i] > 1) {
      ans = ans * 2 % kMod;
    }
  }
  cout << ans << '\n';
  return 0;
}

汪了个汪

构造 找规律

首先 $t=1$ 的条件完全属于 $t=2$，所以直接走 $[1,n]$ 所组成的无序二元组数量为 $\frac{n(n-1)}{2}$，正好对应上了输出的 $\frac{n(n+1)}{2}$ 所组成的 $\frac{n(n-1)}{2}$ 对相邻二元组。所以所有可能的二元组数量都必须用上。

容易将问题转成图论模型：在 $n$ 个点所组成的双向完全图上，找 $n$ 条简单路径，第 $i$ 条路径长 $i$，每条路径分别从 $1,2,\cdots ,n$ 出发，同时互不相等地覆盖了所有的边。

这个问题非常的复杂，我想了两年半才有些许思路。

不难发现在所有二元组 $(i,j)$ 当中，以 $\Delta =|i-j|$ 的大小来分类，$\Delta =1$ 的有 $n-1$ 对，$\Delta =i$ 的有 $n-i$ 对，这正好对应上了跨第 $i$ 列和第 $i+1$ 列的二元组数量是 $n-i$ 个。

所以我们尝试将 $\Delta =i$ 的二元组作用在第 $i$ 列和第 $i+1$ 列当中。具体来说，设某一行第一个数为 $x$，那么这一行的数分别是

$$(x,x\pm 1,x\pm 1\pm 2,\cdots ,x\pm 1\pm 2\pm \cdots \pm (n-1))$$

那么我们可以枚举 $x$ 作为每一行的第一个元素。$\pm$ 的话当然是一正一负，这样可以最大化长度。当值超过 $[1,n]$ 的时候，就不用往后继续生成了。

实操下来，对于 $x\in [1,n]$，生成出来的序列长度正好是 $1\sim n$ 的，于是我们按照长度从小到大的顺序输出即可。

为什么这么生成一定不会产出相同的相邻二元组？

因为第一个数 $x$ 是不一样的。首先行内肯定不会出现相同二元组，因为所有的 $\Delta$ 都不同。对于某行的第 $j$ 个元素，它所形成的二元组和它正上/下方的 $\Delta$ 相同。它相对于 $x$ 的增量都是 $+1-2\cdots \pm j$ 的，但是由于第一个数 $x$ 不相同，所以和上下的二元组肯定是不同的。所以我们不会生成出相同的相邻二元组。

时间复杂度 $\mathcal{O}(n^2)$。

const int kMaxN = 4005;
 
int id[kMaxN], n, t;
vector<vector<int>> ans;
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> t;
  for (int i = 1; i <= n; i++) {
    ans.emplace_back();
    for (int j = 1, x = i; j <= n; j++) {
      ans.back().push_back(x);
      if (j % 2) {
        x += j;
      } else {
        x -= j;
      }
      if (x < 1 || x > n) {
        break;
      }
    }
  }
  for (int i = 0; i < ans.size(); i++) {
    id[ans[i].size()] = i;
  }
  for (int i = 1; i <= n; i++) {
    for (int j : ans[id[i]]) {
      cout << j << ' ';
    }
    cout << '\n';
  }
  return 0;
}

挑战 NPC IV

分治 贪心

我使用的是暴力。暴力计算 $n!$ 个全排列所对应的答案，然后直接 nth_element 求出第 $k$ 大。时间复杂度 $\mathcal{O}(2^{n}n)$，成功获得 $12$ 分。

---

然后是赛后改题环节。

首先对于 $k=1$，排序后第 $i$ 个数会在 $i(n-i+1)$ 个区间当中出现过，所以把 $f(i)$ 小的放中间，$f(i)$ 大的放两边即可。

对于 $f(i)$ 一样的，彼此之间怎么排都不会改变答案。所以当 $n\ge 29$ 时，最小的答案会出现超过 $10^{18}$，此时相当于 $k=1$。

计算方式是令 $cn{t}_i$ 为 $f(j)=i$ 的数量，求 $\prod cn{t}_i!$。事实上你求出来 $n=29$ 时应该是大约 $3\times 10^{17}$，这是因为有些不能完全居中，会偏左或偏右，所以实际上这种情况已经超过 $10^{18}$ 了。

所以对于 $n\ge 29$，我们直接考虑 $k=1$ 特化的 $\mathcal{O}\left({\log }_{2}n\right)$ 做法。直接枚举 $i\in [1,n]$，优先小的的放中间，通过数学计算算出 $i$ 前面的系数并累加。

具体计算方式

计算 $[l,r]$ 的系数，即 $f(l,r)=\sum _{i=l}^{r}i(n-i+1)$。

首先把 $n-i+1$ 拆成 $n+1$ 减去 $i$，应用乘法分配律，得到

$$原式=(n+1)\times \sum _{i=l}^{r}i-\sum _{i=l}^r{i}^2$$

前者应用等差数列求和公式，后者用

$$\sum _{i=1}^{n}i=\frac{n(n+1)(2n+1)}{6}$$

做差即可。得到

$$原式=(n+1)\times \frac{(l+r)(r-l+1)}{2}-\frac{r(r+1)(2r+1)}{6}+\frac{(l-1)l(2l-1)}{6}$$

对于 $n<29$，也是因为最终的答案不超过大约 $10^4$ 这个数量级，所以直接设计状态 $(x_1,x_2,x_3,x_4,x_5,sum)$ 表示 $f(i)=1,2,3,4,5$ 的分别有 $x_1,x_2,x_3,x_4,x_5$ 个，且总优美度为 $sum$ 的合法排列数量。那么我们只需要从小到大枚举 $sum$，计算 $sum$ 对应的数量，就可以找到第 $k$ 小的 $sum$ 了。用记忆化搜索优化常数，规避无用状态。时间复杂度 $\mathcal{O}\left(V\times \prod _{i=1}^5\sum _{j=1}^n[f(j)=i]\right)$，其中 $V$ 表示答案值域，大约 $10^4$。

四暗刻单骑

贪心 线段树 博弈论

我采用的是暴力。令 $1$ 表示当前手可以赢，$0$ 表示不能赢但是可以平局，$-1$ 表示必输。那么爆搜状态 $(i,x,y)$ 就表示当前摸第 $i$ 个牌，当前手手牌为 $x$，对面为 $y$。摸完 $a_i$ 后当前手有两种操作：

1. 不要摸的 $a_i$，直接打出去。
   1. $a_i=y$，那么打出去就直接输了，这种情况值为 $-1$。
   2. 否则递归计算 $(i+1,y,x)$，然后取反（这就是我的值的特殊性，可以直接取相反数交换状态）。
2. 摸了 $a_i$ 攥手里，把 $x$ 打出去。
   1. $x=y$，打出去直接输，值为 $-1$。
   2. 否则递归计算 $(i+1,y,a_i)$， 然后取反。

需要注意搞之前先把 $i>r$ 判了（平局），然后把 $a_i=x$ 判了（必胜）。

不难发现对于相同的 $r$，$(i,x,y)$ 所对应答案是一定的，所以可以做记忆化搜索。时间复杂度 $\mathcal{O}(qn{k}^2)$。成功获得 $20$ 分。