专栏文章

2025-10-11模拟赛总结

lliuyi0905
生活·游记参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minmw66q
此快照首次捕获于
2025/12/02 05:01
3 个月前
此快照最后确认于
2025/12/02 05:01
3 个月前
查看原文

前言

这场比赛前两题的出题人就是我😋终于当上出题人了！
吸取 tyk 上次出题的教训，我决定当一回良心出题人🤔
显然，在 T1 放橙，T2 放蓝是个不错的选择😙 不出意外的没有出意外
好渴鹅、好鱼鱼还有小松鼠巨佬 AK 了 %%%
作为出题人的我当然是没有参赛的🙂 如果这次要写总结，那就只好写一下找题过程、经历和思路好了。

A

听说 T1 要放简单一点，于是乎，我在千万题中选出了它：
呃……不知道去哪了，让我找找（
虽然这道只是橙题，不过我们还是可以发现有不少不多人挂在了 T1😁，果真在意料之中。
这道题有许多细节（好像也不多），比如判断无解，以及是否重复等等。成功让 zrr、wyn、lzh 等幸运儿挂了 \打call
还是讲一下思路吧：
首先考虑无解的情况，我们会发现，若存在 ii 使得 aia_i 不出现在集合 sis_i 中，则必定无解（不可能试出来）。
否则，尝试次数应该为 ∏i=1nvi−k\prod\limits_{i = 1}^n v_i - k。吗？我们发现，若 did_i 不满足每一位都属于正确范围，则 did_i 不合法。所以只需要减去合法的 did_i 数量即可。
再来展示一下美丽的代码：
codeCPP
#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≤18n \le 18，所以 ∏i=1nvi≤1018\prod\limits_{i = 1}^n v_i \le 10 ^ {18}，所以开一个 long long 即可。

B

我可不像 tyk，这道题可是我出的唯一一道数学题，还是非常水的那种。
由于 tyk 出了过多数学题，看不过去了，只好也找了一道数学题，看着还挺不错，既有矩阵又有费马小定理，还有乘法逆元。而且式子推起来也不是很难，估计学过数学的都可以爆切。
话不多说，还是看一下题解吧：
solution

题目分析

可以直接用数学方法做出，也可以用矩阵快速幂通过。这里介绍一种用数学方法的。
首先考虑单独的一行的递推式如何简化：Fi,j=aFi,j−1+bF_{i, j} = a F_{i, j - 1} + b。
为了求出 Fi,mF_{i, m}，也就是数列的通项，我们设 Fi,m+x=a(Fi,m−1+x)F_{i, m} + x = a (F_{i, m - 1} + x)。
不难求出，这里的 x=ba−1x = \frac{b}{a - 1}，得到 Fi,m+ba−1=am−1(Fi,1+ba−1)F_{i, m} + \frac{b}{a - 1} = a ^ {m - 1} (F_{i, 1} + \frac{b}{a - 1})。
进一步化简，可以求得
Fi,m=am−1Fi,1+am−1b−ba−1F_{i, m} = a ^ {m - 1} F_{i, 1} + \frac{a ^ {m - 1} b - b}{a - 1}
接下来考虑 Fn−1,mF_{n - 1, m} 到 Fn,mF_{n, m} 的转化：Fn,1=cFn−1,m+dF_{n, 1} = c F_{n - 1, m} + d。
将其带入一式，得到 Fn,m=am−1(cFn−1,m+d)+am−1b−ba−1F_{n, m} = a ^ {m - 1} (c F_{n - 1, m} + d) + \frac{a ^ {m - 1} b - b}{a - 1}。
化简一下就变成了
Fn,m=am−1cFn−1,m+am−1d+am−1b−ba−1F_{n, m} = a ^ {m - 1} c F_{n - 1, m} + a ^ {m - 1} d + \frac{a ^ {m - 1} b - b}{a - 1}
我们惊喜的发现，只需将 am−1ca ^ {m - 1} c 设为 AA，将 am−1d+am−1b−ba−1a ^ {m - 1} d + \frac{a ^ {m - 1} b - b}{a - 1} 设为 BB。
就可以得到一个与一式一模一样的式子：Fn,m=AFn−1,m+BF_{n, m} = A F_{n - 1, m} + B。
也就是说
Fn,m=An−1F1,m+An−1B−BA−1F_{n, m} = A ^ {n - 1} F_{1, m} + \frac{A ^ {n - 1} B - B}{A - 1}
于是乎，只需用一式算出 F1,mF_{1, m}，再用二式就可以算出 Fn,mF_{n, m} 了！

代码实现与细节处理

我们得到了公式，但还没完呢。
注意到 nn 和 mm 都非常大，1≤n,m≤101061 \le n, m \le 10^{10^6}，所以需要对 nn 和 mm 取模。
  • 当 n,mn, m 作为指数时，根据费马小定理，应对 φ(p)\varphi(p) 取模（109+610 ^ 9 + 6）。
  • 当 n,mn, m 作为系数时，模数应为 pp（109+710 ^ 9 + 7）。
其他的带入公式算一下即可。
注意要特判 a=1a = 1 和 A=1A = 1 的情况，除数不能为 00。
作为良心出题人，特意造了许多 a=1a = 1 或 A=1A = 1 的数据😏 很高兴看到又有不少人被卡了，还有许多 zrr 不会指数取模，咋没看到他们写高精呢🤨
还是太可惜了，好不容易分出了那么多档数据，结果没有一个人去写部分分😡 太生气了
都在学术讨论！给他们讨论了几下，全都会做了！讨厌！
codeCPP
#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 只是压了一点行，就被管家活活打断了双腿（
谨慎观看CPP
#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 就被骂惨了），是不是默认我是良心出题人了😚

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...