题目：[[2024.10.21 题目]]
## 串串串
有两个长度为 $n,m$ 的 $0/1$ 字符串 $S,T$，给定 $Q$ 次询问，每次询问给出 $(l_1,r_1,l_2,r_2)$，其中 $r_1-l_1=r_2-l_1$，令 $a=S_{l_1\sim r_1},b=T_{l_2\sim r_2}$，求 $a_i\ne b_i$ 的位置数量对 $2$ 取模的结果。
---
手推可以发现，交换区间内的任意两个位置 $i,j$，答案的奇偶性都是不变的。具体而言：如果位置 $i$ 与位置 $j$ 相等，那么交换了就跟没交换一样；如果两个位置上的数不一样，那么答案可能会根据实际情况加 $2$ 或减 $2$，答案的奇偶性没有变化。
因此我们只需要使用两个前缀和数组记录 $S$ 和 $T$ 任意区间的 $1$ 的数量，如果询问的两个区间 $1$ 的数量相等就输出 $0$，否则输出 $1$。
```cpp
// 出题人，柠檬熟了
#include <fstream>
using namespace std;
using LL = long long;
const LL kMaxN = 2e5 + 5;
ifstream cin("string.in");
ofstream cout("string.out");
LL p1[kMaxN], p2[kMaxN], n, m, q;
char s[kMaxN], t[kMaxN];
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> (s + 1) >> (t + 1) >> q;
for (LL i = 1; i <= n; i++) {
p1[i] = p1[i - 1] + (s[i] == '1');
}
for (LL i = 1; i <= m; i++) {
p2[i] = p2[i - 1] + (t[i] == '1');
}
for (LL l1, r1, l2, r2; q; q--) {
cin >> l1 >> r1 >> l2 >> r2;
cout << (LL)((p1[r1] - p1[l1 - 1]) % 2 != (p2[r2] - p2[l2 - 1]) % 2) << '\n';
}
return 0;
}
```
## 方格计数
给定 $H,W$，有 $(H+1)\times (W+1)$ 的网格，现在要在网格上找 $N$ 个不同的结点，使得这些点在同一条直线上，并且在这条直线上相邻点的距离不小于 $D$，求方案数对 $10^9+7$ 取模的值。
---
枚举 $N$ 个点分别在哪个位置上肯定不行，因此我们不如枚举 $N$ 个点所在的直线上。很容易想到枚举直线的斜率，然后再枚举直线上的两个端点，在算出答案。但是这样子代码过于复杂，而且枚举斜率很容易重复。
小学老师交过我们一件事：「两点确定一条直线」。这也就意味着我们根本就没有必要枚举直线的斜率，我们可以直接枚举直线两边的端点，即可确定这一条直线/线段。根据初中老师所讲的知识，假设两点之间 $x$ 坐标差值为 $\Delta x$，$y$ 坐标差值为 $\Delta y$，则这两点之间连接的线段将会在网格上经过 $\gcd(\Delta x,\Delta y)$ 个点。
此时我们已经选择了两个端点，因此还需要选择 $N-2$ 个直线上的端点。由于题目中指出相邻两点距离至少为 $D$，因此我们将直线经过的点编号，令任意相邻两个点编号差不能小于 $l$，这时学过组合数的都应该知道了，答案为
$
\binom{g-(l-1)\times (N-3)-2\times k+1}{N-2}
$
因此我们预处理杨辉三角用来计算组合数，或者预处理阶乘使用费马小定理计算组合数（因为在这题当中模数为质数）。此时时间复杂度为 $\mathcal O(W^2H^2)$，可以通过 $30$ 分。
接下来考虑如何得到满分，其实非常简单。不难发现，在枚举的过程中，有很多直线它们斜率相等或互为倒数，这时我们就可以把这些直线看成相等的，同一枚举并计算。假设有一个矩形框，这条直线就是矩形的对角线，矩形的宽为 $w$，高为 $h$，则为同样的矩形有 $(W-w+1)(H-h+1)$ 个，乘上即可。
最后就是细节的处理了。对于 $h,w\ne 0$ 的矩形，我们需要将答案翻倍，很明显是因为对角线有 $2$ 条。这样我们就成功地将时间复杂度优化到了 $\mathcal O(WH)$，可以通过 $100$ 分。
```cpp
#include <fstream>
#include <cmath>
using namespace std;
using LL = long long;
const LL kMaxN = 3005, kMod = 1e9 + 7;
ifstream cin("count.in");
ofstream cout("count.out");
LL c[kMaxN][kMaxN], f[kMaxN], t, n, w, h, d, ans;
void pre() {
cin.tie(0)->sync_with_stdio(0);
c[0][0] = 1; // 没有初始化
for (LL i = 1; i <= 3000; i++) {
c[i][0] = 1;
for (LL j = 1; j <= i; j++) {
c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % kMod;
}
}
// f[0] = 1;
// for (int i = 1; i <= 3000; i++) {
// f[i] = f[i - 1] * i % kMod;
// }
}
LL gcd(LL a, LL b) { return !b ? a : gcd(b, a % b); }
double dis(LL x, LL y) { return sqrt(x * x + y * y); }
// LL pow(LL a, LL b) {
// LL res = 1;
// for (; b; b /= 2) {
// b & 1 && (res = res % a % kMod);
// a = a * a % kMod;
// }
// return res;
// }
//
// LL inv(LL x) { return pow(x, kMod - 2); }
LL fuck(LL i, LL j) {
LL g = gcd(i, j), l = (LL)ceil(1.0 * d / dis(i / g, j / g)) /* 差 */;
if ((n - 1) * l > g) { return 0; }
return c[g - (n - 3) * (l - 1) - 2 * l + 1][n - 3 + 1] * // 组合数
(i && j ? 2 : 1) % kMod * // 一正一反
(w - i + 1) % kMod * // 横方向
(h - j + 1) % kMod; // 竖方向
}
int main() {
pre();
for (cin >> t; t; t--) {
cin >> n >> w >> h >> d;
// BYD 的，没有特判调了半小时，我 /* */
if (n == 1) {
cout << (w + 1) * (h + 1) << '\n';
continue;
}
ans = 0;
for (LL i = 0; i <= w; i++) {
for (LL j = 0; j <= h; j++) {
if (!i && !j) {
continue;
}
ans = (ans + fuck(i, j)) % kMod;
}
}
cout << ans << '\n';
}
return 0;
}
```
## 树数树
有 $n$ 个结点的树，现在求一个最长的序列 $a$，满足：
- $\forall i\in(1,m]$，$a_i$ 为 $a_{i-1}$ 的祖先或 $a_{i-1}$ 为 $a_i$ 的祖先；
- $\forall 1\le i<j\le m$，$a_i\ne a_j$。
$T$ 组数据。
---
不会写，只判断了树为链或菊花的情况，获得 $30$ 分，赛后发现没有特判完全二叉树的形状，本来能拿 $40$ 分。本体正解合并堆（左偏树），虽然好渴鹅学过，但是没有发现！你干嘛——哈哈哎哟~
## 序列
对于数 $S$，它的数位和为 $10$ 的字段被称作 se 序列，如果它的被一个数位都至少在一个 se 序列中，则称 $S$ 是 II 数。给定 $n$ 和 $b_i$ $(i\in [0,10))$，令 $a_i=\cfrac{b_i}{\sum\limits_{j=0}^9 b_j}$（满足 $\sum\limits_{i=0}^9a_i=1$），随机生成一个 $[0,10^n)$ 范围内的数，每一位上生成数字 $i$ 的概率为 $a_i$，求这个数为 II 数的概率，答案对 $10^9+7$ 取模。
---
不会写，对于 $n=1$ 的情况特判并输出 $0$，在 widwolf 上面理所应当地获得了 $5$ 分的好成绩，但是在 lemon 上面没有分，老师说题面改了（具体的可以查看 [[2024.10.21 星期一]]），不知道最后在 linux 上面能够获得多少分，反正都一样。
## 总结
- **排名**：$4$；
- **比赛分数**：$235/400$；
- **情况**：相比 [[2024.10.20 模拟赛]]，还可以；
- **问题**：突然不会左偏树的应用了。