赛中过题：ABEG。
A - Car Show
给定一个长为 $n$ 的颜色序列 $\{a_i\}$，问有多少段区间出现了所有的颜色？
分析
双指针。对于右端点 $r$，若临界的左端点是 $l$，那么 $[1, l]$ 都是合法的。
队友签的，代码没有。
B - Two Frogs
在一个长为 $n$ 的池塘中，可以从第 $i$ 个荷叶跳到第 $[i + 1, i + a_i]$ 个荷叶上。
若两个青蛙从 $1$ 开始，每个荷叶上随机往后跳，问相同步数到达第 $n$ 个荷叶的期望。
分析
显然 DP。设 $DP(i, j)$ 为跳 $i$ 次跳到第 $j$ 个荷叶上的概率，往后刷表即可。
int main() {
int n;
cin >> n;
vector<int> v(n + 1);
vector<Z> iv(n + 1);
for (int i = 1; i <= n; i++) {
cin >> v[i];
iv[i] = Z(v[i]).inv();
}
vector<Z> dp(n + 1);
dp[1] = 1;
Z ans = 0;
for (int i = 1; i <= n; i++) {
vector<Z> ndp(n + 1);
auto add = [&](int u, Z x) {
if (u <= n)
ndp[u] += x;
};
for (int j = 1; j <= n; j++) {
Z u = dp[j] * iv[j];
add(j + 1, u);
add(j + v[j] + 1, -u);
}
for (int j = 1; j <= n; j++) {
ndp[j] += ndp[j - 1];
}
dp = ndp;
ans += dp[n] * dp[n];
}
cout << ans;
return 0;
}
E - Longest Increasing Subsequence
构造一个长为 $n$ 的排列，使得其恰好有 $m$ 个最长上升子序列。
分析
考虑二进制。我们可以在序列最后放置两个较大的数，使得 LIS 恰好翻倍。
但是若当前为为 $1$，我们需要考虑怎么才能恰好加 $1$ 而又不影响后面。
可以考虑放置一些较小的数，使得其只可能与较小的数形成 LIS，并且后面仍可继承翻倍。
我为了方便编写，使用 front = 60 和 back = -60，最后离散化一下就是排列。
void solve() {
ll n;
cin >> n;
vector<int> v;
int front = 60, back = -60;
bool f = true;
int cnt = 0, back_begin = back;
for (int i = 31; i >= 0; i--) {
if ((1ll << i) > n) {
continue;
} else if (f) {
v.push_back(back);
back += 1;
cnt += 1;
f = false;
continue;
}
v.push_back(front + 1);
v.push_back(front);
front += 2;
if ((n >> i) & 1) {
while (back - back_begin <= cnt) {
v.push_back(back++);
}
}
cnt++;
}
auto ret = func(v);
cout << ret.size() << '\n';
for (auto ri : ret) {
cout << ri << ' ';
}
cout << '\n';
}
F - Matrix and GCD
给定一个 $n \times m$ 的矩阵 $M_{ij}$，其值为 $1, \cdots, nm$ 的排列，求其所有子矩阵的 $\gcd$ 之和。
TODO