2025.8.4 模拟赛

宝石展览

数学 组合数学

首先看到要求所有方案的总和，我们就很容易想到将贡献拆开来进行计算。因为不同种宝石之间的选择是互不影响的，因此我们可以算出每一种宝石在自身不同情况下的总贡献，再乘上其它宝石的选择方案数，累加起来即可得到答案。

假设当前枚举到的宝石是 $(a,v)$，那么如果要选 $i$ $(1\le i\le a)$ 颗宝石，由于组内每颗宝石是互不相同的，因此选择方案数是 $\left(\genfrac{}{}{0ex}{}{a}{i}\right)$，单个方案贡献是 $v^i$，再乘上其它宝石的选择方案数，从而当前宝石的贡献是

$$\sum _{i=1}^a\left(\genfrac{}{}{0ex}{}{a}{i}\right)v^i\times \frac{\prod _{i=1}^n{2}^{a_i}}{2^a}$$

把 $i=0$ 时也给加上，然后再在后面减去一个 $1$

$$\left(\sum _{i=0}^a\left(\genfrac{}{}{0ex}{}{a}{i}\right)v^i-1\right)\times \frac{\prod _{i=1}^n{2}^{a_i}}{2^a}$$

此时眼尖的就发现了，这是一个二项式定理的形式，应用它就可以转化成

$$\left((v+1{)}^a-1\right)\times \frac{\prod _{i=1}^n{2}^{a_i}}{2^a}$$

右边的部分可以转化为前缀乘积乘上后缀乘积的形式，或者使用费马小定理算出 $2^a$ 的逆元。最后将每个宝石的贡献累加起来就可以求出正确答案。时间复杂度 $\mathcal{O}(n{\log }_{2}V)$。

#include <iostream>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 2e5 + 5, kMod = 1e9 + 7;
 
LL a[kMaxN], v[kMaxN], pre[kMaxN], suf[kMaxN], n, ans;
 
// 快速幂
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;
}
 
int main() {
  cin >> n;
  for (LL i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (LL i = 1; i <= n; i++) {
    cin >> v[i];
  }
  // 前缀和
  pre[0] = 1;
  for (LL i = 1; i <= n; i++) {
    pre[i] = pre[i - 1] * pow(2, a[i]) % kMod;
  }
  // 后缀和
  suf[n + 1] = 1;
  for (LL i = n; i >= 1; i--) {
    suf[i] = suf[i + 1] * pow(2, a[i]) % kMod;
  }
  // 应用结论
  for (LL i = 1; i <= n; i++) {
    ans = ans + pre[i - 1] * suf[i + 1] % kMod * (pow(v[i] + 1, a[i]) - 1) % kMod;
    ans = (ans % kMod + kMod) % kMod;
  }
  cout << ans << '\n';
  return 0;
}

乘积

序列dp 数学 容斥 质因数分解

首先本题想要满足 $A$ 中每一个元素都是 $n$ 的因数还是非常简单的。如果 $n$ 的因数个数是 $d$，那么所有满足该条件的序列的数量是 $d^{2m}$。

然后我们需要考虑怎么求出 $\prod A\le n^m$ 的 $A$ 的个数。我们将所有的 $A$ 对应集合拆成三个集合 $S_{<}$、$S_{=}$ 和 $S_{>}$，而我们最终求的答案是 $|S_{<}|+|S_{=}|$。这个显然是不好求的，考虑从 $S_{>}$ 下手，从总数减去 $S_{>}$，但还是毫无头绪。

我们从 $S_{<}$ 中任意取一个 $A$，建立一个新的序列 $A^{\prime }|A_i^{\prime }=\frac{n}{A_i}$，可以发现新的序列 $A^{\prime }$ 也是一个满足所有元素都是 $n$ 的因数的序列，而由于每一个 $A_i$ 乘上 $A_i^{\prime }$ 都等于 $n$，因此 $\prod A\times \prod A^{\prime }=n^{2m}$。又因为 $A\in S_{<}$，也就是 $\prod A<n^m$，可以得出结论 $\prod A^{\prime }>n^m$，也就是 $A^{\prime }$ 一定是 $S_{>}$ 里面的序列。

通过上述方法，对于 $S_{<}$ 中的任意序列，我们都可以让其对应到 $S_{>}$ 中的一个序列；同理，$S_{>}$ 中的任意序列也可以对应到 $S_{<}$。因此 $|S_{<}|=|S_{>}|$。

综上，我们只需要计算所有满足因数条件的序列数量 $d^{2m}$，减去满足因数条件、所有乘积正好等于 $n^m$ 的序列个数 $|S_{=}|$，即可得到 $|S_{<}|+|S_{>}|$，又它俩是相等的，因此将其除以 $2$ 可以得到 $|S_{<}|$，最后加上 $|S_{=}|$ 得到 $|S_{\le }|$。这也等价于 $\frac{d^{2m}+|S_{=}|}{2}$。

于是问题就转化成了如何求出 $|S_{=}|$ 的数量。对 $n$ 进行质因数分解，可以发现每个质因数的选择过程都是独立的。如果一个质因数在 $n$ 中出现了 $k$ 次，那么在最终的序列中这个质因数需要乘上 $k\times m$ 次，因为要求乘积是 $n^m$。

可以使用 dp 算出单个质因数 $(x,k)$（分别表示质因数、质因数在 $n$ 中出现次数） 的选择方法个数。设 $d{p}_{i,j}$ 表示为在前 $i$ 个数当中当前质因数乘了 $j$ 次，那么如果要选第 $i+1$ 个数的话，当前质因数乘的数量不能超过 $k$（因为 $a_{i+1}$ 要满足 $a_{i+1}|n$）次，最少可以选择让 $a_i$ 乘 $0$ 次，因此状态转移方程

$$d{p}_{i+1,j+p}\leftarrow d{p}_{i+1,j+p}+d{p}_{i,j}(0\le p\le k)$$

写成收集型就是

$$d{p}_{i,j}=\sum _{p=0}^{k}d{p}_{i-1,j-p}(0\le p\le k,j)$$

直接转移时间复杂度是 $\mathcal{O}(m(km{)}^2)$ 的，会被 $n=2^{29}$ 这样的数据卡掉（此时 $k$ 等于 $29$）。考虑优化转移，不难发现求和部分是一个滑动窗口，动态地维护和的值就行了，如果 $j>k$ 就把 $j-k-1$ 给撇掉。

因此 dp 时间复杂度为 $\mathcal{O}(m^{2}k)$，总时间复杂度为 $\mathcal{O}(\sum _x{m}^{2}k)$，最坏只有 $x$ 为 $2$，$k$ 为 $29$，此时也是非常优秀的。

#include <iostream>
#include <map>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 1e6 + 5, kMod = 998244353;
 
LL dp[kMaxN], nxt[kMaxN], ans = 1, add = 1, n, m, len;
map<LL, LL> f;
 
// 分解质因数
void split(LL n) {
  for (LL i = 2; i * i <= n; i++) {
    for (; n % i == 0; n /= i) {
      f[i]++;
    }
  }
  if (n > 1) {
    f[n]++;
  }
}
 
// 快速幂
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;
}
 
// 逆元
LL inv(LL x) {
  return pow(x, kMod - 2);
}
 
// 对于一个在 n 中出现过 e 次的质因数，求方案数
LL solve(LL e, LL m) {
  LL mx = len * e;
  fill(dp, dp + mx + 1, 0);
  dp[0] = 1;
  for (LL i = 1; i <= len; i++) {
    LL pre = 0;
    for (LL j = 0; j <= mx; j++) {
      pre = (pre + dp[j]) % kMod;
      // 撇掉过时状态
      if (j > e) {
        pre = ((pre - dp[j - e - 1]) % kMod + kMod) % kMod;
      }
      nxt[j] = pre;
    }
    // 滚动数组还原，也可以不滚
    for (LL j = 0; j <= mx; j++) {
      dp[j] = nxt[j];
    }
  }
  if (m * e > mx) {
    return 0;
  }
  return dp[m * e];
}
 
int main() {
  cin >> n >> m;
  len = 2 * m;
  split(n);
  for (auto &i : f) {
    ans = ans * (i.second + 1) % kMod;  // 计算因数个数
  }
  ans = pow(ans, len);  // 初始答案
  for (auto &i : f) {
    add = add * solve(i.second, m) % kMod;  // 注意是乘积
  }
  ans = (ans + add) % kMod * inv(2) % kMod;  // 应用结论
  cout << ans << '\n';
  return 0;
}

平面点集划分

由于我跑去写 T4 了，因此 T3 只写了一个超级大暴力。

阻碍

最短路

本题我最终没有调出来，但是我的思路是正确的。

首先，我们将其中一条边边权 $+2$，但是最终的最短路却是 $+1$，这代表着改了之后一定不会经过这条边。因此，题目等价于删掉一条边，新的最短路是原来的最短路 $+2$。

最短路和次短路的长度还是很好求的，如果次短路长度不等于最短路长度 $+1$ 的话直接输出 $0$。求完之后对于任意一条 $1\sim n$ 的路径，如果它的长度正好是最短路/次短路，那么我们就把所有的这些路径合并起来，形成一个最短路 DAG/次短路 DAG，使得在这个 DAG 上 $1\sim n$ 任意路径的长度都是最短路/次短路。

显然的是，我们删除的边一定是在最短路 DAG 上的一条边，但是有没有可能删掉这条边之后仍然存在另外一条路径长度等于最短路呢？此时 DAG 就有用了。定义 DAG 一条边如果删掉使得 DAG 不连通的话，那么这条边就被成为大动脉。我们就是需要删除一条最短路 DAG 上的大动脉使得最短路不复存在。

那么次短路呢？有可能次短路和最短路共用一段边，我们删掉最短路之后导致次短路也没了。因此我们还需要判断删除的一条边是否是次短路 DAG 上的大动脉，如果是的话就不能删。

问题就变成了怎么求最短路/次短路 DAG 的大动脉了，可以正着一遍拓扑排序+反着一遍拓扑排序，求出 $1\sim i$ 的路径数量和 $n\sim i$ 的路径数量，最后枚举边 $(u,v)$，如果 $1\sim u$ 的路径数量乘上 $v\sim n$ 的路径数量正好是所有的路径数量，那么 $(u,v)$ 就是大动脉。

我趋势的原因是求次短路的 DAG。

总结

总分 $100+100+25+20=245$。

前两题我自认为做得还是不错的，在 $30$ 分钟内成功 AC 掉了，但是我后面一直再想最后一题，但是由于我的思路是有缺陷的因此一直没有调试出来，导致我根本没有时间去写第三题，最后我还是交的暴力，相当于浪费一个半小时。其实第三题的 $\mathcal{O}(n^2)$ 的算法是相对简单的，并且能够获得 $80$ 分。下次模拟赛我需要更理性地安排时间，不要想到一个不知道是否正确的思路就立马去写，写了发现很难调或疑似错误就要及时收手，把时间安排在能够安稳地获得更多分数的题目上。