并非周考。
B - Carousel of Combinations
https://codeforces.com/problemset/problem/1957/E
\(q\) 次询问，每次给定一个 \(n\)，求：
\[ \left(\sum\limits_{i=1}^n\sum\limits_{j=1}^i \dfrac {i!}{(i-j)!\cdot j!}\bmod j\right) \bmod 10^9+7 \]
\(n,q\le 10^6\)。
赛时打表 \(\dfrac {i!}{(i-j)!\cdot j!}\bmod j\) 易发现只有 \(j=4\) 或 \(j\) 为质数的列上有值；且仅当 \(\left\lfloor \dfrac ij\right\rfloor\) 发生变化时，\((i,j)\) 的值不同。
于是乎埃筛找每个 \(j\) 的倍数，由于每个值会持续一段 \(i\) 上的区间，考虑维护差分数组。前缀和得到原数组，再前缀和就能得到答案。
证明
考虑转化为组合数形式方便证明。当 \(j\) 为质数时：
\[ \begin{aligned} \dfrac {i!}{(i-j)!\cdot j!}\bmod j &=C_i^j\cdot (j-1)!\bmod j\\ &=C_{i\bmod j}^{j\bmod j}\cdot C_{\lfloor \frac ij\rfloor}^{\frac jj}\cdot (j-1)!\bmod j\\ &=\left\lfloor \frac ij\right\rfloor\cdot (j-1)!\bmod j\\ &=\left\lfloor \frac ij\right\rfloor\cdot (j-1)\bmod j \end{aligned} \]
当 \(j\) 为合数时：
\[ \dfrac {i!}{(i-j)!\cdot j!}\bmod j=\left\lfloor \frac ij\right\rfloor\cdot (j-1)!\bmod j \]
当 \(j=p^2\)，其中 \(p\) 为质数时：
- 当 \(j\ne 4\) 时，\(\dfrac jp \ge 3\)，代表在 \(1\sim j-1\) 中至少出现了两个 \(p\) 的倍数，即 \((j-1)\bmod j = 0\)。
- 否则，原式转化为 \(2\cdot \left\lfloor \frac i4\right\rfloor\bmod 4\)。
否则：可以找到至少一组 \(j=i\cdot k\) 满足 \(i\ne k\)，则 \(i,k\) 出现在 \(1\sim j-1\) 中，即 \((j-1)\bmod j = 0\)。
得到上述结论。
Tips：
- 卢卡斯定理：懒得写了。
- 威尔逊定理：对于质数 \(p\)，\((p-1)!\equiv -1\pmod p\)。
C - 玻利维亚 / Bolivija
https://www.luogu.com.cn/problem/P12401
给定若干次区间的插入与删除操作，对于所有值域内未被覆盖极长段 \(i\)，令 \(len_i\) 为其长度；每次操作后询问 \(\sum \frac {len_i\cdot (len_i-1)}2+len_i\)。
来一点新奇的思路。假如你和我一样，很不幸地不知道维护最小值这个 trick，怎么解决这道题？
容易想到线段树维护节点内贡献和左侧、右侧极长未覆盖长度。加入区间是简单的：对于线段树上被完全覆盖的节点，更新其贡献为 \(0\)。依次 pushup 即可。
删除区间，对于被这段区间完全覆盖的节点，发现如果整体被覆盖次数减少 \(1\)，有可能出现新的、未被覆盖的点，如果暴力 check 左右儿子是否出现了这样的点并更新，复杂度就不太美观了。
故而对于一个节点，将『完全覆盖它的区间』和『部分覆盖它的区间』分开考虑，在维护该节点所有实时信息（记为 \(s\)）的同时，维护另一份只考虑了『部分覆盖它地区间』的信息（记为 \(s'\)）：
如果一个『部分覆盖它的区间』被删除：
- 如果存在『完全覆盖它的区间』：\(s\) 不变；向下修改儿子的 \(s\)，\(s'\) 需要从儿子的 \(s\) 更新。
如果一个『完全覆盖它的区间』被删除：
- 如果还存在其他『完全覆盖它的区间』：\(s,s'\) 都不变。
- 如果不存在其他『完全覆盖它的区间』：用 \(s'\) 更新 \(s\)。
这样就能 \(O(q\log V)\) 解决上述问题。本方法较维护最小值的优势在于——似乎没有。想了许多种情况，它们大抵是等价的——且本方法更难写（哭）。
#include <bits/stdc++.h>
const int maxn = 654205;
struct {
int cnt;
long long u, s;
int l, r, lu, ru, ls, rs;
} t[maxn << 2];
#define lt (p << 1)
#define rt (lt | 1)
#define len(p) (t[p].r - t[p].l + 1)
void pushup(int p) {
t[p].s = t[lt].u + t[rt].u + (long long)t[lt].ru * t[rt].lu;
if (t[lt].lu == len(lt))
t[p].ls = len(lt) + t[rt].lu;
else
t[p].ls = t[lt].lu;
if (t[rt].ru == len(rt))
t[p].rs = t[lt].ru + len(rt);
else
t[p].rs = t[rt].ru;
if (!t[p].cnt)
t[p].u = t[p].s, t[p].lu = t[p].ls, t[p].ru = t[p].rs;
return;
}
void bld(int p, int l, int r) {
t[p].l = l, t[p].r = r;
if (l == r) {
t[p].u = t[p].s = 1ll;
t[p].lu = t[p].ru = t[p].ls = t[p].rs = 1;
return;
}
int mid = (l + r) >> 1;
bld(lt, l, mid), bld(rt, mid + 1, r);
pushup(p);
return;
}
void add(int p, int l, int r) {
if (l <= t[p].l && t[p].r <= r) {
++t[p].cnt, t[p].u = 0ll, t[p].lu = t[p].ru = 0;
return;
}
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid)
add(lt, l, r);
if (r > mid)
add(rt, l, r);
pushup(p);
return;
}
void rem(int p, int l, int r) {
if (l <= t[p].l && t[p].r <= r) {
if (!--t[p].cnt)
t[p].u = t[p].s, t[p].lu = t[p].ls, t[p].ru = t[p].rs;
return;
}
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid)
rem(lt, l, r);
if (r > mid)
rem(rt, l, r);
pushup(p);
return;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
int n, q;
std::cin >> n >> q;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++i)
std::cin >> a[i];
int u = (n + 1) / 2;
const int N = a[u];
bld(1, 1, N);
for (int i = 1; i < u; ++i)
if (a[i] != a[n - i + 1])
add(1, std::min(a[i], a[n - i + 1]) + 1, std::max(a[i], a[n - i + 1]));
std::cout << t[1].u << '\n';
for (int i, v; q--; ) {
std::cin >> i >> v;
if (a[i] != a[n - i + 1])
rem(1, std::min(a[i], a[n - i + 1]) + 1, std::max(a[i], a[n - i + 1]));
a[i] = v;
if (a[i] != a[n - i + 1])
add(1, std::min(a[i], a[n - i + 1]) + 1, std::max(a[i], a[n - i + 1]));
std::cout << t[1].u << '\n';
}
return 0;
}D - 移动金币
https://www.luogu.com.cn/problem/P5363
最后一个棋子的移动等价于丢掉最后一部分空格；中间棋子的移动等价于把左边间隔里的一段空格拿到右边的间隔里。发现原问题转化为『阶梯 Nim 博弈』。
关于阶梯 Nim 博弈…
给定 \(n\) 层石头，每次行动可以选择以下操作中的一种：
- 选择 \(2\le i\le n\)，从第 \(i\) 层石头中拿走若干颗，全部放到第 \(i-1\) 层里。
- 从第 \(1\) 层石头中拿走若干颗，全部丢弃。
不能行动者输。
本问题可以等效为 Nim 游戏：
对于第偶数层，若 Alice 选择从第 \(2i\) 层中移动 \(x\) 个石头到 \(2i-1\)，Bob 可以立即从 \(2i-1\) 层中将这 \(x\) 个石头移动到 \(2i-2\)（或丢弃）。
也就是说，Alice 在偶数层中的操作不会对 Bob 带来任何限制。偶数层的石头可以被视作不存在；从奇数层移动到偶数层的石头可以被视为丢弃；进而，奇数堆中的移动等效为『丢弃』，将原问题中所有奇数堆抽离出来，等效成普通的 Nim 游戏。
问题转化成，将 \(n-m\) 个元素放到编号 \(0\sim m+1\) 的盒子里，满足奇数号盒子球个数异或和为 \(0\) 的方案数。小容斥一下，用总数减去异或和为 \(0\) 者。