2024.10.9 模拟赛

题目：2024.10.9 题目

矩阵交换

有 $n\times m$ 的整数矩阵 $a$，每个元素均为 $1,2,3$。可以选择任意两不相等的行，将它们交换，使得每一列 $i$ 均单调不减 $a_{j,i}\le a_{j+1,i}$ $(1\le j<n)$。

---

我们对于每一个行，使用第一个不相等的列上的数为关键字从小到大进行排序，排序完之后每一行与下一行第一个不相等的列肯定是小于等于的（废话）。此时我们对于每一列进行清扫，如果发现不满足条件那也无可厚非，因为每一行都已经锁死了，直接输出无解。如果没有这种情况，输出有解即可。

#include <fstream>
#include <algorithm>
 
using namespace std;
 
const int kMaxN = 105;
 
ifstream cin("exchange.in");
ofstream cout("exchange.out");
 
int t, n, m;
 
struct Line {
  int a[kMaxN];
 
  int &operator[](int p) {
    return a[p];
  }
 
  friend bool operator<(const Line &a, const Line &b) {
    for (int i = 1; i <= m; i++) {
      if (a.a[i] != b.a[i]) {
        return a.a[i] < b.a[i];
      }
    }
    return 1;
  }
} a[kMaxN];
 
int main() {
  for (cin >> t; t; t--) {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        cin >> a[i][j];
      }
    }
    sort(a + 1, a + n + 1);
    bool b = 1;
    for (int i = 1; i <= m && b; i++) {
      for (int j = 2; j <= n && b; j++) {
        if (a[j - 1][i] > a[j][i]) {
          b = 0;
        }
      }
    }
    cout << (b ? "YES" : "NO") << '\n';
  }
  return 0;
}

砖块摆放

有 $n$ 个砖块，第 $i$ 个砖块颜色为 $s_i$（用 $\text{A,B,C}$ 表示，转换成数字为 $0,1,2$）。进行 $n-1$ 次变换，每次变换会将元素数量 $n$ 变为 $n-1$。设 $a$ 为变换前的序列，则变换后的序列 $b$ 满足 $b_i=-(a_i+a_{i+1})\mathrm{mod}3$。

---

我们观察 $-(a_i+a_{i+1})\mathrm{mod}3$ 这个式子，可以将 $\mathrm{mod}3$ 去掉最后做（因为取模的性质），然后再将负号去掉，因为负负得正，有偶数个负号即可消掉，因此仅当 $2|n$ 时答案需要额外加上负号。

观察 $a_i+a_{i+1}$，不难发现它跟杨辉三角非常相像。令 $T_{i,j}$ 为杨辉三角内第 $i$ 行第 $j$ 列的数，那么可以画图找到规律对于答案 $a_i$ 的系数正好为 $T_{i,j}$。又 $\left(\genfrac{}{}{0ex}{}{i-1}{j-1}\right)=T_{i,j}$，因此我们需要快速求组合数。

因为模数 $3$ 是质数，因此考虑费马小定理求逆元（$a^{p-1}\equiv 1(\mathrm{mod}p)$，其中 $p$ 为质数，通过变换得到 $a^{p-2}\equiv \frac{1}{a}(\mathrm{mod}p)$）。由于 $\left(\genfrac{}{}{0ex}{}{n}{m}\right)=\frac{n!}{m!(n-m)!}$，因此我们预处理 $i!$ $(0\le i\le n)$，然后通过费马小定理将 $\frac{1}{a}$ 转化成 $a_{p-2}$，即 $\times a$，接着就可以使用公式快速求出 $\left(\genfrac{}{}{0ex}{}{n}{m}\right)$，将其转化为系数累加。

但是在实际的实现当中我们会出现很大的问题。比如 $\frac{4!}{3!}$（等同于 $\frac{24}{12}$），我们使用费马小定理将原式转化为 $24\times 12$，然后对 $3$ 取模……变成 $0$ 了，但是我们直接使用除法可以得到 $4\mathrm{mod}3=1$。这时我们垂死病中惊坐起，突然发现小丑竟是我自己，因为费马小定理使用不仅需要 $p$ 为质数，还要求 $a\perp b$。同样地，拓展欧几里得求逆元也不能用。你干嘛~哈哈哎哟——

这时我们突然发现我们之前求组合数模数都很大，今天的模数特别小只有 $3$，因此可以手推卢卡斯定理，然后通过递归不断缩小，如果 $n,m$ 较小就直接暴力求。这样，我们就以 $\mathcal{O}(n{\log }_{3}n)$ 的可爱时间复杂度成功过题了。

#include <fstream>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 2e5 + 5;
 
ifstream cin("brick.in");
ofstream cout("brick.out");
 
LL a[kMaxN], t, n, ans;
char s[kMaxN];
 
LL C(LL n, LL m) {
  if (n < m) {
    return 0;
  }
  LL res = 1;
  for (LL i = n - m + 1; i <= n; i++) {
    res *= i;
  }
  for (LL i = 1; i <= m; i++) {
    res /= i;
  }
  return res % 3;
}
 
LL fuck(LL n, LL m) {
  if (n < m) {
    return 0;
  }
  if (n <= 10) {
    return C(n, m);
  }
  return fuck(n / 3, m / 3) * C(n % 3, m % 3) % 3;
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  for (cin >> t; t; t--) {
    cin >> n >> (s + 1), ans = 0;
    for (LL i = 1; i <= n; i++) {
      a[i] = s[i] == 'A' ? 0 : s[i] == 'B' ? 1 : 2;
    }
    for (LL i = 1; i <= n; i++) {
      ans = ans + (fuck(n - 1, i - 1) * a[i] % 3) % 3;
    }
    n % 2 || (ans = (-ans % 3 + 3) % 3);
    cout << (ans == 0 ? 'A' : ans == 1 ? 'B' : 'C') << '\n';
  }
  return 0;
}

学习 LIS

有长度为 $n$ 的数组 $a$，满足 $\forall i\le n,a_i\in [1,m]$。已知对于数组 $a$ 的位置 $i$，以 $i$ 结尾的最长上升子序列长度为 $l_i$，求满足条件的 $a$ 的数量。

---

使用暴力，通过 dfs 给每一个数都选择可能得值，在搜的时候就使用可行性剪枝去掉不满足条件的数。对于每一个数，一共有 $m$ 种选择，需要选择 $n$ 个数，因此最坏时间复杂度为 $\mathcal{O}(m^n)$，但是由于使用了可行性剪枝完全可以骗过 $1\le n,m\le 10$ 的数据。好渴鹅考场的写法写错了，炸裂 $0$ 分。

战略轰炸

没有完全看懂题目，连文件都没有创建，$0$ 分。出题人，我爱你❤。

总结

• 排名：$2$；
• 比赛分数：$200/400$；
• 情况：相比 2024.10.7 模拟赛，一般；
• 问题：序列 dp 能力较弱。