这场有点大份，被喷惨了，谁家C1C2出这个。
B
题目大意：Alice跟Bob正在玩追逐游戏，Alice想要抓住Bob，游戏地点是一个长度为 $n$ 的环，初始时Alice位于位置 $a$ ，Bob位于位置 $b$ ，每秒钟，Bob可以移动到相邻的位置，也可以原地不动，在整个游戏过程中，Bob最多可以移动 $k$ 次，观察到Bob的动作后，Alice可以移动到相邻的位置，也可以原地不动，如果此时两人在同一个位置，那么就抓住了。
现在双方都采取最优策略，问Bob最晚多少秒内能被抓住？
数据范围：$2 \leq n \leq 10^8$。
思路：首先特判一下 $n \leq 3$ 的情况，这点很多人被坑了。
随后，模拟可知，两个人无非是沿最短路追，等到Bob无法移动了，就只有Alice动了，于是得到答案。
| |
C1
题目大意：给定一个非负整数 $a$ 和一个长度为 $n$ 的非空严格递增数字序列 $d$ ，其中 $0 \leq d_i \leq 9$ ，请求出仅由 $d$ 中数字组成的非负整数 $b$ 中，使得 $|a-b|$ 最小的值。
注意：在本题中， $n=2$ 。
数据范围：$0 \leq a \leq 10^{17},0 \leq d_i \leq 9$。
思路：跟C2同一份代码，建议直接左转C2思路。
| |
C2
题目大意：给定一个非负整数 $a$ 和一个长度为 $n$ 的非空严格递增数字序列 $d$ ，其中 $0 \leq d_i \leq 9$ ，请求出仅由 $d$ 中数字组成的非负整数 $b$ 中，使得 $|a-b|$ 最小的值。
数据范围：$0 \leq a \leq 10^{17},0 \leq d_i \leq 9$。
思路：赛时联想到之前的这道题R1077-D ，然后就是只要考虑当前比 $a$ 少一位的情况，高一位的情况，而同一位的情况可以从高位到低位做数位DP，状态定义为当前是否大于、等于或者小于当前的数，即可（其实可以直接从那题拉板子）。
| |
D
题目大意：平面上有 $n$ 个不同的整点，其中第 $i$ 个点位于 $(x_i,y_i)$ 处，现在要给这些点着色，选择两个整数 $k_1,k_2$ ， $x \leq k_1, y > k_2$ 的被染成红色， $x > k_1, y > k_2$ 的被染成绿色， $x \leq k_1, y \leq k_2$ 的被染成蓝色， $x > k_1, y \leq k_2$ 的被染成黄色，现在问：有多少种不同的染色方式？
数据范围：$4 \leq n \leq 2 \cdot 10^6,1 \leq x_i,y_i \leq n$。
思路：这题的这个读入数据被骂惨了，oier净想着卡常。
很显然会想到对 $x$ 排序，使用类似哈希表（但是2e6会被卡，所以这里依旧采用我们熟悉的数组滑窗套路），考虑在 $x_i,x_{i+1}$ 之间画出一条竖线，此时想到，如何才能画出一条竖线？
画图很显然地可以看出，上限是左半部分的上限跟右半部分的上限的最小值，下限是左半部分的下限跟右半部分的下限的最大值，于是预先把 $y$ 都收集起来，二分查找就可以得到答案了,这里可以用前后缀处理，跑得快一点。
| |
E1
题目大意：给你一个区间，里面的 $-1$ 是待填空位，用非负整数填充，使得整个区间总和恰好等于 $m$ ，对每种合法填法，计算每个前缀和的平方和，然后把所有填法的结果加起来取模。
注意本题不带修，操作是诈骗的，E2是带修的。
数据范围：$1 \leq n \leq 3 \cdot 10^5,-1 \leq a_i \leq 10^6$。
思路：很显然地，我们会联想到隔板法，同时维护普通前缀和，跟当前的未知个数，然后很自然地进入推式子环节。
不妨设 $pre_i$ 为已知的前缀和， $x_i$ 为当前未知位置的前缀和贡献，于是有
$$ \sum_{\text{合法填法}}\sum_{i=l}^{r}(pre_i+x_i)^2 $$展开平方可得：
$$ (pre_i+x_i)^2=pre_i^2+2pre_ix_i+x_i^2 $$所以答案可以分成三部分分别计算。
令当前区间中未知位置个数为 $k$ ，待填入未知位置的总和为 $N$ ，也就是代码中的 $N=m-pr$ ，若 $N < 0$ 则无解。由于每个未知数都是非负整数，所以合法方案数可以写成生成函数取系数：
$$ [z^N]\left(\frac{1}{1-z}\right)^k=\binom{N+k-1}{k-1} $$记这个值为 $cnt0$ 。
于是第一部分就是：
$$ \sum_{\text{合法填法}}pre_i^2=cnt0 \cdot pre_i^2 $$接下来考虑 $\sum x_i$ 。对于一个固定前缀 $i$ ，如果这个前缀中有 $c_i$ 个未知位置，那么 $x_i$ 就是这 $c_i$ 个未知数的和。先考虑其中某一个未知数 $y$ 的总贡献，它对应的带权生成函数为：
$$ \left(\sum_{y\geq 0}yz^y\right)\left(\frac{1}{1-z}\right)^{k-1} =\frac{z}{(1-z)^{k+1}} $$于是：
$$ \sum_{\text{合法填法}}y=[z^N]\frac{z}{(1-z)^{k+1}}=\binom{N+k-1}{k} $$记这个值为 $cnt1$ ，那么：
$$ \sum_{\text{合法填法}}x_i=c_i \cdot cnt1 $$最后考虑 $\sum x_i^2$ 。设前缀中的未知数分别为 $y_1,y_2,\cdots,y_{c_i}$ ，则有：
$$ x_i^2=\sum_{j=1}^{c_i}y_j^2+2\sum_{1 \leq j先考虑单个未知数的平方项，它的生成函数为：$$ \left(\sum_{y\geq 0}y^2z^y\right)\left(\frac{1}{1-z}\right)^{k-1} =\frac{z(1+z)}{(1-z)^{k+2}} $$所以：
$$ \sum_{\text{合法填法}}y_j^2 =[z^N]\frac{z(1+z)}{(1-z)^{k+2}} =\binom{N+k}{k+1}+\binom{N+k-1}{k+1} $$又因为：
$$ \binom{N+k}{k+1}=\binom{N+k-1}{k}+\binom{N+k-1}{k+1} $$记：
$$ cnt2=\binom{N+k-1}{k+1} $$就有：
$$ \sum_{\text{合法填法}}y_j^2=cnt1+2cnt2 $$再考虑两个不同未知数的乘积项：
$$ \left(\sum_{y_j\geq 0}y_jz^{y_j}\right)\left(\sum_{y_q\geq 0}y_qz^{y_q}\right)\left(\frac{1}{1-z}\right)^{k-2} =\frac{z^2}{(1-z)^{k+2}} $$所以：
$$ \sum_{\text{合法填法}}y_jy_q=[z^N]\frac{z^2}{(1-z)^{k+2}}=\binom{N+k-1}{k+1}=cnt2 $$代回 $x_i^2$ ，就能得到：
$$ \sum_{\text{合法填法}}x_i^2 =c_i(cnt1+2cnt2)+2\binom{c_i}{2}cnt2 =c_i \cdot cnt1+c_i(c_i+1)cnt2 $$因此，对于每个前缀 $i$ ，贡献为：
$$ cnt0 \cdot pre_i^2+2pre_i(c_i \cdot cnt1)+c_i \cdot cnt1+c_i(c_i+1)cnt2 $$这也就对应代码里的：
$$ cnt0=\binom{N+k-1}{k-1},\quad cnt1=\binom{N+k-1}{k},\quad cnt2=\binom{N+k-1}{k+1} $$以及每次枚举前缀时维护的 $pre_i$ 和 $c_i$ 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79const ll MOD = 998244353; constexpr int MX = 1e6 + 1; ll F[MX]; // 预处理阶乘 ll INV_F[MX]; // 预处理逆元 ll qpow(ll x, int n) { ll res = 1; for (; n; n >>= 1) { if (n % 2) res = res * x % MOD; x = x * x % MOD; } return res; } auto init = [] { F[0] = 1; for (int i = 1; i < MX; i++) F[i] = F[i - 1] * i % MOD; // 预处理阶乘 INV_F[MX - 1] = qpow(F[MX - 1], MOD - 2); for (int i = MX - 1; i; i--) { INV_F[i - 1] = INV_F[i] * i % MOD; } // 预处理逆元 return 0; }(); // 计算C(n,m),即从n个数中取m个数 ll comb(int n, int m) { return m < 0 || m > n ? 0 : F[n] * INV_F[m] % MOD * INV_F[n - m] % MOD; } void solve() { ll n, q, op, l, r, m; cin >> n >> q; vl a(n + 1); rep(i, 1, n) cin >> a[i]; vl cnt(n + 1); vl pre(n + 1); rep(i, 1, n) { pre[i] = pre[i - 1]; cnt[i] = cnt[i - 1]; if (a[i] == -1) cnt[i]++; else pre[i] = (pre[i - 1] + a[i]); } rep(v, 0, q - 1) { cin >> op >> l >> r >> m; ll tem = cnt[r] - cnt[l - 1]; ll pr = pre[r] - pre[l - 1]; ll ans = 0; if (pr > m) { cout << 0 << endl; return; } if (tem == 0) { if (pr != m) { cout << 0 << endl; return; } ll tem2 = 0; rep(i, l, r) { tem2 = (tem2 + a[i]) % MOD; ans = (ans + tem2 * tem2 % MOD) % MOD; } cout << ans << endl; return; } ll tem2 = 0; ll tem3 = 0; ll cnt0 = comb(m - pr + tem - 1, tem - 1); ll cnt1 = comb(m - pr + tem - 1, tem); ll cnt2 = comb(m - pr + tem - 1, tem + 1); rep(i, l, r) { if (a[i] == -1) tem3++; else tem2 = (tem2 + a[i]) % MOD; ll tem4 = tem3 * cnt1 % MOD; ll tem5 = (tem4 + tem3 * (tem3 + 1) % MOD * cnt2 % MOD) % MOD; ans = (ans + cnt0 * tem2 % MOD * tem2 % MOD) % MOD; ans = (ans + 2 * tem2 % MOD * tem4 % MOD + tem5) % MOD; } cout << ans << endl; } return; }