2025-10-11模拟赛总结

· · 生活·游记

前言

这场比赛前两题的出题人就是我😋终于当上出题人了！

吸取 tyk 上次出题的教训，我决定当一回良心出题人🤔

显然，在 T1 放橙，T2 放蓝是个不错的选择😙 不出意外的没有出意外

好渴鹅、好鱼鱼还有小松鼠巨佬 AK 了 %%%

作为出题人的我当然是没有参赛的🙂 如果这次要写总结，那就只好写一下找题过程、经历和思路好了。

A

听说 T1 要放简单一点，于是乎，我在千万题中选出了它：

呃……不知道去哪了，让我找找（

虽然这道只是橙题，不过我们还是可以发现有不少不多人挂在了 T1😁，果真在意料之中。

这道题有许多细节（好像也不多），比如判断无解，以及是否重复等等。成功让 zrr、wyn、lzh 等幸运儿挂了 \打call

还是讲一下思路吧：

首先考虑无解的情况，我们会发现，若存在 i 使得 a_i 不出现在集合 s_i 中，则必定无解（不可能试出来）。

否则，尝试次数应该为 \prod\limits_{i = 1}^n v_i - k。吗？我们发现，若 d_i 不满足每一位都属于正确范围，则 d_i 不合法。所以只需要减去合法的 d_i 数量即可。

再来展示一下美丽的代码：

::::success[code]

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
LL n, k, c = 1;
string v, s[20];
int main() {
  cin >> n >> k >> v;
  for (int i = 0, m; i < n; i++) {
    cin >> m >> s[i], c *= m;
    s[i].find(v[i]) == string::npos && (cout << -1, exit(0), 1);
  }
  for (string t; k; k--) {
    cin >> t;
    bool f = 1;
    for (int i = 0; i < n; i++)
      s[i].find(t[i]) == string::npos && (f = 0);
    c -= f;
  }
  cout << c;
  return 0;
}

::::

因为 n \le 18，所以 \prod\limits_{i = 1}^n v_i \le 10 ^ {18}，所以开一个 long long 即可。

B

我可不像 tyk，这道题可是我出的唯一一道数学题，还是非常水的那种。

由于 tyk 出了过多数学题，看不过去了，只好也找了一道数学题，看着还挺不错，既有矩阵又有费马小定理，还有乘法逆元。而且式子推起来也不是很难，估计学过数学的都可以爆切。

话不多说，还是看一下题解吧：

::::info[solution]

题目分析

可以直接用数学方法做出，也可以用矩阵快速幂通过。这里介绍一种用数学方法的。

首先考虑单独的一行的递推式如何简化：F_{i, j} = a F_{i, j - 1} + b。

为了求出 F_{i, m}，也就是数列的通项，我们设 F_{i, m} + x = a (F_{i, m - 1} + x)。

不难求出，这里的 x = \frac{b}{a - 1}，得到 F_{i, m} + \frac{b}{a - 1} = a ^ {m - 1} (F_{i, 1} + \frac{b}{a - 1})。

进一步化简，可以求得

F_{i, m} = a ^ {m - 1} F_{i, 1} + \frac{a ^ {m - 1} b - b}{a - 1}

接下来考虑 F_{n - 1, m} 到 F_{n, m} 的转化：F_{n, 1} = c F_{n - 1, m} + d。

将其带入一式，得到 F_{n, m} = a ^ {m - 1} (c F_{n - 1, m} + d) + \frac{a ^ {m - 1} b - b}{a - 1}。

化简一下就变成了

F_{n, m} = a ^ {m - 1} c F_{n - 1, m} + a ^ {m - 1} d + \frac{a ^ {m - 1} b - b}{a - 1}

我们惊喜的发现，只需将 a ^ {m - 1} c 设为 A，将 a ^ {m - 1} d + \frac{a ^ {m - 1} b - b}{a - 1} 设为 B。

就可以得到一个与一式一模一样的式子：F_{n, m} = A F_{n - 1, m} + B。

也就是说

F_{n, m} = A ^ {n - 1} F_{1, m} + \frac{A ^ {n - 1} B - B}{A - 1}

于是乎，只需用一式算出 F_{1, m}，再用二式就可以算出 F_{n, m} 了！

代码实现与细节处理

我们得到了公式，但还没完呢。

注意到 n 和 m 都非常大，1 \le n, m \le 10^{10^6}，所以需要对 n 和 m 取模。

其他的带入公式算一下即可。

注意要特判 a = 1 和 A = 1 的情况，除数不能为 0。

::::

作为良心出题人，特意造了许多 a = 1 或 A = 1 的数据😏 很高兴看到又有不少人被卡了，还有许多 zrr 不会指数取模，咋没看到他们写高精呢🤨

还是太可惜了，好不容易分出了那么多档数据，结果没有一个人去写部分分😡 太生气了

都在学术讨论！给他们讨论了几下，全都会做了！讨厌！

::::success[code]

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int M = 1e9 + 7, P = M - 1;
LL n, m, p, q, a, b, c, d;
string s, t;
LL C(LL x, LL y) {
  LL r = 1;
  for (; y; x = x * x % M, y >>= 1) y & 1 && (r = r * x % M);
  return r;
}
int main() {
  cin >> s >> t >> a >> b >> c >> d;
  for (auto v : s)
    n = (n * 10 % M + v - '0') % M, p = (p * 10 % P + v - '0') % P;
  for (auto v : t)
    m = (m * 10 % M + v - '0') % M, q = (q * 10 % P + v - '0') % P;
  LL k = C(a, (q - 1 + P) % P);
  LL o = (a > 1 ? (k * b % M - b + M) % M * C(a - 1, M - 2) % M : (m - 1 + M) % M * b % M);
  LL A = k * c % M, B = (k * d % M + o) % M;
  LL v = C(A, (p - 1 + P) % P);
  LL h = (A > 1 ? (v * B % M - B + M) % M * C((A - 1 + M) % M, M - 2) % M : (n - 1 + M) % M * B % M);
  cout << ((k + o) % M * v % M + h) % M;
  return 0;
}

::::

ly 只是压了一点行，就被管家活活打断了双腿（

::::warning[谨慎观看]

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int M = 1e9 + 7, P = M - 1;
LL n, m, p, q, a, b, c, d;
string s, t;
LL C(LL x, LL y) {
  LL r = 1;
  for (; y; x = x * x % M, y >>= 1) y & 1 && (r = r * x % M);
  return r;
}
int main() {
  cin >> s >> t >> a >> b >> c >> d;
  for (auto v : s) n = (n * 10 % M + v - '0') % M, p = (p * 10 % P + v - '0') % P;
  for (auto v : t) m = (m * 10 % M + v - '0') % M, q = (q * 10 % P + v - '0') % P;
  cout << ((C(a, (q - 1 + P) % P) + (a > 1 ? (C(a, (q - 1 + P) % P) * b % M - b + M) % M * C(a - 1, M - 2) % M : (m - 1 + M) % M * b % M)) % M * C(C(a, (q - 1 + P) % P) * c % M, (p - 1 + P) % P) % M + (C(a, (q - 1 + P) % P) * c % M > 1 ? (C(C(a, (q - 1 + P) % P) * c % M, (p - 1 + P) % P) * (C(a, (q - 1 + P) % P) * d % M + (a > 1 ? (C(a, (q - 1 + P) % P) * b % M - b + M) % M * C(a - 1, M - 2) % M : (m - 1 + M) % M * b % M)) % M % M - (C(a, (q - 1 + P) % P) * d % M + (a > 1 ? (C(a, (q - 1 + P) % P) * b % M - b + M) % M * C(a - 1, M - 2) % M : (m - 1 + M) % M * b % M)) % M + M) % M * C((C(a, (q - 1 + P) % P) * c % M - 1 + M) % M, M - 2) % M : (n - 1 + M) % M * (C(a, (q - 1 + P) % P) * d % M + (a > 1 ? (C(a, (q - 1 + P) % P) * b % M - b + M) % M * C(a - 1, M - 2) % M : (m - 1 + M) % M * b % M)) % M % M)) % M;
  return 0;
}

::::

C and D

神秘人出的，也挺简单的，不过没有做。

后记

我出的题确实还是挺简单的，还好没有人来骂我（tyk 就被骂惨了），是不是默认我是良心出题人了😚