C - Clamp Clamp Clamp
简要题意.
给定正整数 \(N\)，对于 \(\{0, 1, \dots, 2N\}\) 的排列 \(a=(a_0, a_1, \dots, a_{2N})\)，\(a\in A\) 当且仅当对 \(i=0,\dots,N-1\) 满足 \(a_{2i+1} < a_{2i+2}\)。
对 \(a\in A\) 定义 \(f(a)\) 如下：
设 \(b_0=a_0\)；
对于 \(i=0,\dots,N-1\)，设 \(b_{i+1}=\min\{\max\{b_i, a_{2i+1}\}, a_{2i+2}\}\)；
定义 \(f(a) = b_N\)。
给定 \(Q\) 个整数 \(Z_1, \dots, Z_Q\)，对于 \(j=1,\dots,Q\)，求出 \(|\{a\mid f(a) = Z_j \land a\in A\}|\)。模 \(998244353\)。
\(1 \le N \le 10^7\)，\(1 \le Q \le 2.5\times 10^5\)。
记 \(l_i = a_{2i+1}, r_i = a_{2i+2}\)，则 \(f(a)\) 一个形象的意义就是将 \(b_0\) 每次先尝试拉到 \(l_i\) 再尝试拉到 \(r_i\)。
考虑极大的 \(k\) 满足后 \(k\) 个区间的交非空而后 \(k+1\) 个区间的交为空。记交为 \([l, r]\)，若 \(r_{N-k-1}<l\) 则 \(f(a)=l\)，否则 \(f(a)=r\)。若不存在 \(k\)，则交集必然包含 \(N\)，进一步必有 \(f(a)=N\)。
考虑 \(r_{N-k-1}<l\)，固定 \(k, l\) 可以如下计算：
从 \(k\) 个区间中选取一个左端点为 \(l\)；
剩下 \(k-1\) 个区间左端点 \(< l\)，所有 \(k\) 个右端点 \(> l\)；
倒数第 \(k+1\) 个区间左端点 \(<\) 右端点 \(< l\)；
其余区间任选。
有计算式
\[ k \cdot l^{\underline{k-1}} \cdot (2N-l)^{\underline k} \cdot \binom{l+1-k}2 \cdot 2^{-(N-k-1)} (2N-2k-1)! \]
化简可以得到
\[ l! (2N-l)! k 2^{-(N-k)} \binom{2N-2k-1}{l-k-1} \]
定义
\[ f_{l, s, t} = \sum_{k=1}^{N-1} k^s 2^k \binom{2N-2k-t}{l-k-1} \qquad (s, t \in \{0, 1\}) \]
则 \(f_{l+1,*,*}\) 容易从 \(f_{l,*,*}\) 递推得到。
还要考虑没有 \(k\) 的情况，考虑先枚举 \(a_0\) 再分配左右端点，容易数出这样的 \(a\) 有 \((2N+1)(N!)^2\) 种。
E - Exponent of PI
简要题意.
给定两两互质的正整数 \(A, B, C\)，记 \(N_k\) 是集合 \(\{n \mid n=x^{BC}y^{CA}z^{AB}\land x, y, z \in \mathbb Z^+\}\) 中第 \(k\) 小的元素。
则可以证明 \(\sum_{k\ge 1} \frac1{N_k^2}\) 是 \(\frac pq \pi^e\) 的形式，其中 \(p, e\) 是整数，\(q\) 是正整数。求出 \(\frac pq\) 在模 \(998244353\) 意义下的结果和 \(e\)。
\(1 \le A, B, C \le 250\)。
记集合 \(I = \{i \mid i=BCu + CAv + ABw \land u, v, w \in \mathbb N\}\)，则答案为 \(\prod_p \sum_{i\in I} p^{-2i}\)。
考虑先求出 GF \(F(x) = \sum_{i\in I} x^i\)，再考虑把它改成 DGF。记方案数的 GF 是
\[ G(x) = \frac1{(1-x^{BC})(1-x^{CA})(1-x^{AB})} \]
考虑 \(i \bmod ABC\) 可以确定 \(u \bmod A, v \bmod B, w \bmod C\)，因此 \(0, \dots, ABC-1\) 内的合法的数的 GF 是
\[ \frac{(1-x^{ABC})^3}{(1-x^{BC})(1-x^{CA})(1-x^{AB})} \]
而 \(F(x)\) 就是其除一个 \(1-x^{ABC}\)，即
\[ F(x) = \frac{(1-x^{ABC})^2}{(1-x^{BC})(1-x^{CA})(1-x^{AB})} \]
因此 DGF 就是
\[ \frac{\zeta(2BC)\zeta(2CA)\zeta(2AB)}{\zeta(2ABC)^2} \]
查阅 Wikipedia 可以知道
\[ \zeta(2n) = \frac{(-1)^{n+1}B_{2n}(2\pi)^{2n}}{2(2n)!} \]
其中 \(B_{2n}\) 是 Bernouli Number 的第 \(2n\) 项。使用载谭 Binomial Sum 求解即可。
H - How to Pose Such a Problem
简要题意.
给定 \(N\) 和 \(4\times 4\) 的矩阵 \(W_{0\dots3, 0\dots3}\)，保证 \(W_{0,0}=0\)。
从 \((0, 0)\) 开始，每一步可以走 \((i, j)\) \((0 \le i, j \le 3)\)，权值是 \(W_{i,j}\)。一条路径的权值是每一步的权值之积。
对于 \(k=1,2,\dots,N\)，求出走到 \((k, k)\) 且不触碰直线 \(y=x-1\) 的路径的权值之和。\(2 \le N \le 2.5\times 10^5\)，\(W_{i, j}\) 随机。
令 \(F(x, y) = \sum_{0\le i,j \le 3} W_{i,j} x^i y^j\)。
令 \(g_k\) 是从 \((0, 0)\) 走到 \((k, k)\) 且中途不触碰 \(y=x\) 的权值和，\(G(x)\) 是其 OGF，则答案就是 \(\frac1{1-G(x)}\)。
不妨把一步 \((i, j)\) 看成 \(i\) 个 \(+1\) 和 \(j\) 个 \(-1\)，那么不触碰直线 \(y=x-1\) 的所有路径的所有本质不同的循环移位，和任意游走的路径的所有本质不同的循环移位，的集合相等（懒得组织语言了，读者可以结合代数部分理解）。
计数本质不同的无限制游走的循环移位，只需要考虑把当前在最开头那一步看成第一步，则答案为
\[ [x^k y^k] \frac{\sum_{0\le i, j\le 3} (i+j) W_{i, j} x^i y^j}{1-F(x, y)} \]
二元有理 GF 的对角线是 D-Finite 的。可以暴力高斯消元。
而有限制游走的循环移位，则考虑将第一个 \(G(x)\) 的结构循环移位，即
\[ [x^k] \frac{\sum_{j\ge 1} 2j \cdot g_j x^j}{1-G(x)} = [x^k] \frac{2xG'(x)}{1-G(x)} \]
则我们现在有 \(H(x) = \frac{xG'(x)}{1-G(x)}\)，要求 \(\frac1{1-G(x)}\)。容易解得 \(\frac1{1-G(x)} = \exp\left(\int_0^x t^{-1}H(t) \,\mathrm dt\right)\)。