题目：[[2024.10.9 题目]]
## 矩阵交换
有 $n\times m$ 的整数矩阵 $a$，每个元素均为 $1,2,3$。可以选择任意两不相等的行，将它们交换，使得每一列 $i$ 均单调不减 $a_{j,i}\le a_{j+1,i}$ $(1\le j<n)$。
---
我们对于每一个行，使用第一个不相等的列上的数为关键字从小到大进行排序，排序完之后每一行与下一行第一个不相等的列肯定是小于等于的（废话）。此时我们对于每一列进行清扫，如果发现不满足条件那也无可厚非，因为每一行都已经锁死了，直接输出无解。如果没有这种情况，输出有解即可。
```cpp
#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$（用 $\texttt{A,B,C}$ 表示，转换成数字为 $0,1,2$）。进行 $n-1$ 次变换，每次变换会将元素数量 $n$ 变为 $n-1$。设 $a$ 为变换前的序列，则变换后的序列 $b$ 满足 $b_i=-(a_i+a_{i+1})\bmod 3$。
---
我们观察 $-(a_i+a_{i+1})\bmod 3$ 这个式子，可以将 $\bmod 3$ 去掉最后做（因为取模的性质），然后再将负号去掉，因为负负得正，有偶数个负号即可消掉，因此仅当 $2|n$ 时答案需要额外加上负号。
观察 $a_i+a_{i+1}$，不难发现它跟杨辉三角非常相像。令 $T_{i,j}$ 为杨辉三角内第 $i$ 行第 $j$ 列的数，那么可以画图找到规律对于答案 $a_i$ 的系数正好为 $T_{i,j}$。又 ${} \tbinom{i-1}{j-1}=T_{i,j} {}$，因此我们需要快速求组合数。
因为模数 $3$ 是质数，因此考虑费马小定理求逆元（$a^{p-1}\equiv 1\pmod p$，其中 $p$ 为质数，通过变换得到 ${} a^{p-2}\equiv \cfrac{1}{a}\pmod p {}$）。由于 $\tbinom{n}{m}=\cfrac{n!}{m!(n-m)!}$，因此我们预处理 $i!$ $(0\le i\le n)$，然后通过费马小定理将 $\cfrac{1}{a}$ 转化成 $a_{p-2}$，即 $\times a$，接着就可以使用公式快速求出 $\tbinom{n}{m}$，将其转化为系数累加。
但是在实际的实现当中我们会出现很大的问题。比如 $\cfrac{4!}{3!}$（等同于 $\cfrac{24}{12}$），我们使用费马小定理将原式转化为 $24\times 12$，然后对 $3$ 取模……变成 $0$ 了，但是我们直接使用除法可以得到 $4\bmod 3=1$。这时我们垂死病中惊坐起，突然发现小丑竟是我自己，因为费马小定理使用不仅需要 $p$ 为质数，还要求 $a\perp b$。同样地，拓展欧几里得求逆元也不能用。你干嘛~哈哈哎哟——
这时我们突然发现我们之前求组合数模数都很大，今天的模数特别小只有 $3$，因此可以手推卢卡斯定理，然后通过递归不断缩小，如果 $n,m$ 较小就直接暴力求。这样，我们就以 $\mathcal O(n\log_3 n)$ 的可爱时间复杂度成功过题了。
$\binom{n}{m}\equiv \binom{\lfloor n/p\rfloor}{\lfloor m/p\rfloor}\times\binom{n\bmod p}{m\bmod p}\pmod p
$
```cpp
#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 能力较弱。