2025.10.11 模拟赛

密码

枚举 字典树

首先密码中的每一位要求属于该位的尝试列表，否则永远试不出正确代码。然后对于 $k$ 个已经试过的密码，先给它们去重，然后判断是否每一位均属于尝试列表，如果是就对答案减一即可。时间复杂度 $\mathcal{O}(nk)$。

#include <fstream>
#include <unordered_set>
#include <string>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 1e4 + 5;
 
ifstream cin("password.in");
ofstream cout("password.out");
 
LL n, k, sum = 1;
string s[kMaxN], a, t;
unordered_set<string> st;
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> k >> a;
  a = " " + a;
  for (LL i = 1, x; i <= n; i++) {
    cin >> x >> s[i];
    sum *= x;
    if (s[i].find(a[i]) == string::npos) {
      cout << "-1\n";
      return 0;
    }
  }
  for (LL i = 1; i <= k; i++) {
    cin >> t;
    t = " " + t;
    if (st.count(t)) {
      continue;
    }
    st.insert(t);
    bool b = 1;
    for (LL j = 1; j <= n && b; j++) {
      b &= s[j].find(t[j]) != string::npos;
    }
    if (b) {
      sum--;
    }
  }
  cout << sum << '\n';
  return 0;
}

矩阵游戏

等比数列求和 快速幂 乘法逆元

令 $f(x)=ax+b,g(x)=cx+d$，若每一行的第一个元素为 $x$（第一行为 $1$）那么每一行的最后一个元素等于 $f^{m-1}(x)$（迭代 $m-1$ 次），而下一行的第一个元素为 $g(f^{m-1}(x))$。对于同一个一次函数的嵌套 $f^n(x)$，暴力拆开得到等于

$$a^n+b\sum _{i=0}^{n-1}{a}^i$$

通过等比数列求和公式计算。算出 $g(f^{m-1}(x))$ 的系数之后再对其进行 $n-1$ 次迭代，得到第 $n$ 行的第一个元素，然后再带入 $f(x)$ 进行 $m-1$ 次迭代即可。

注意本题 $\log (n/m)$ 达到 $10^6$，所以直接跑十进制的快速幂即可。等比数列求和注意系数为一的特殊情况。

#include <fstream>
#include <utility>
#include <string>
 
using namespace std;
using LL = long long;
 
const LL kMod = 1e9 + 7;
 
ifstream cin("matrix.in");
ofstream cout("matrix.out");
 
LL a, b, c, d;
string n, m;
 
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 pow(LL a, string n) {
  LL b = a, res = 1;
  for (; n.size(); n.pop_back()) {
    if (n.back() != '0') {
      res = res * pow(b, n.back() - '0') % kMod;
    } 
    b = pow(b, 10);
  }
  return res;
}
 
LL num(const string &n) {
  LL res = 0;
  for (char c : n) {
    res = (res * 10 + c - '0') % kMod;
  }
  return res;
}
 
pair<LL, LL> calc(const string &n, LL a, LL b) {
  if (a == 1) {
    return {1, num(n) * b % kMod};
  }
  return {pow(a, n), (pow(a, n) - 1 + kMod) % kMod * pow(a - 1, kMod - 2) % kMod * b % kMod};
}
 
void sub(string &s) {
  s.back()--;
  for (LL i = s.size() - 1; i >= 0; i--) {
    if (s[i] < '0') {
      s[i] += 10, s[i - 1]--;
    }
  }
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m >> a >> b >> c >> d;
  sub(n), sub(m);
  auto p1 = calc(m, a, b);
  auto p2 = calc(n, p1.first * c % kMod, (p1.second * c % kMod + d) % kMod);
  cout << (p1.first * (p2.first + p2.second) % kMod + p1.second) % kMod << '\n';
  return 0;
}

兴趣排列

数学

首先可以简单地写出 $\mathcal{O}(n^2)$ 的 DP。

先判无解，对于 $a_1\ne 0$ 是无解的，$a_i<a_{i-1}$ 也是，其次有 $a_i<n$。

设 $[l,r]$ 表示前 $i$ 个元素的值域区间，那么有 $r-l=i$。如果 $a_i=a_{i-1}$，那么对于任意 $[l,r]$ 区间都不变，只需要在区间内选择一个没选过的即可；否则对于 $[l,r]$ 均可以像两边的任意一边拓展。

所以只需要先让 $ans\leftarrow 1$，然后对于 $i\ge 2$，有

$$ans\leftarrow \{\begin{array}{ll}ans\times [(a_i+1)-(i-1)]& \text{if}{a}_i=a_{i-1}\\ ans\times 2& \text{if}{a}_i>a_{i-1}\end{array}$$

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

#include <fstream>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 2e6 + 5, kMod = 1e9 + 7;
 
ifstream cin("perm.in");
ofstream cout("perm.out");
 
LL a[kMaxN], dp[kMaxN], f[kMaxN], t, n;
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  for (cin >> t; t; t--) {
    cin >> n;
    for (LL i = 1; i <= n; i++) {
      cin >> a[i];
    }
    if (a[1]) {
      cout << "0\n";
      continue;
    }
    bool b = 1;
    for (LL i = 2; i <= n && b; i++) {
      b &= a[i] >= a[i - 1];
      b &= a[i] <= n - 1;
    }
    if (!b) {
      cout << "0\n";
      continue;
    }
    LL ans = 1;
    for (LL i = 2; i <= n; i++) {
      if (a[i] == a[i - 1]) {
        ans = ((a[i] + 1) - (i - 1) + kMod) % kMod * ans % kMod;
      } else {
        ans = ans * 2 % kMod;
      }
    }
    cout << ans << '\n';
  }
  return 0;
}

交换礼物

离散化 序列dp

首先考虑对于一个已有的序列，如何计算最多能让多少位选手开心，等价于最小化不开心的选手数量。不难发现若其出现次数最多的数的出现次数 $x$ 小于等于 $n/2$ 时，每个选手按照手上礼物编号排一排再递给往后的 $x$ 个人，那么不会有人礼物编号重复；否则若其它类型的礼物数量为 $y=n-x$，那么会有 $x-y$ 个人不开心。

所以我们并不需要构造最终的序列，只需要搞清楚哪种礼物有多少人拥有即可。这是典型的计数问题。设 $d{p}_i$ 表示第 $i$ 个序列需要计入到最终序列 $d{p}_i$ 次，那么首先 $d{p}_n$ 为 $1$。从前往后按照下标拓扑序遍历，然后对于所有由两个序列拼起来的序列，让 $d{p}_x\leftarrow d{p}_x+d{p}_i,d{p}_y\leftarrow d{p}_y+d{p}_i$。最后统计到 map（也可以像我一样离散化），求出众数和总数即可。

时间复杂度 $\mathcal{O}(n+k{\log }_{2}k)$。

#include <fstream>
#include <algorithm>
#include <vector>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 1e6 + 5;
 
ifstream cin("gifts.in");
ofstream cout("gifts.out");
 
struct Node {
  LL o, x, y;
  vector<LL> v;
} a[kMaxN];
 
LL dp[kMaxN], f[kMaxN], val[kMaxN], t, n, m;
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  for (cin >> t; t; t--) {
    cin >> n;
    m = 0;
    for (LL i = 1, k; i <= n; i++) {
      cin >> a[i].o;
      if (a[i].o == 1) {
        cin >> k;
        a[i].v.resize(k);
        for (LL &j : a[i].v) {
          cin >> j;
          val[++m] = j;
        }
      } else {
        cin >> a[i].x >> a[i].y;
        a[i].v.clear();
      }
    }
    sort(val + 1, val + m + 1);
    m = unique(val + 1, val + m + 1) - val - 1;
    fill(f + 1, f + m + 1, 0);
    fill(dp + 1, dp + n + 1, 0);
    dp[n] = 1;
    for (LL i = n; i >= 1; i--) {
      if (a[i].o == 2) {
        dp[a[i].x] += dp[i];
        dp[a[i].y] += dp[i];
      }
    }
    for (LL i = 1; i <= n; i++) {
      if (a[i].o == 1) {
        for (LL j : a[i].v) {
          f[lower_bound(val + 1, val + m + 1, j) - val] += dp[i];
        }
      }
    }
    LL sum = 0, mx = 0;
    for (LL i = 1; i <= m; i++) {
      sum += f[i];
      mx = max(mx, f[i]);
    }
    LL other = sum - mx;
    if (mx <= other) {
      cout << sum << '\n';
    } else {
      cout << sum - (mx - other) << '\n';
    }
  }
  return 0;
}