C - Clamp Clamp Clamp
简要题意.
给定正整数 N，对于 {0,1,…,2N} 的排列 a=(a0,a1,…,a2N)，a∈A 当且仅当对 i=0,…,N−1 满足 a2i+1<a2i+2。
对 a∈A 定义 f(a) 如下：
设 b0=a0；
对于 i=0,…,N−1，设 bi+1=min{max{bi,a2i+1},a2i+2}；
定义 f(a)=bN。
给定 Q 个整数 Z1,…,ZQ，对于 j=1,…,Q，求出 |{a∣f(a)=Zj∧a∈A}|。模 998244353。
1≤N≤107，1≤Q≤2.5×105。
记 li=a2i+1,ri=a2i+2，则 f(a) 一个形象的意义就是将 b0 每次先尝试拉到 li 再尝试拉到 ri。
考虑极大的 k 满足后 k 个区间的交非空而后 k+1 个区间的交为空。记交为 [l,r]，若 rN−k−1<l 则 f(a)=l，否则 f(a)=r。若不存在 k，则交集必然包含 N，进一步必有 f(a)=N。
考虑 rN−k−1<l，固定 k,l 可以如下计算：
从 k 个区间中选取一个左端点为 l；
剩下 k−1 个区间左端点 <l，所有 k 个右端点 >l；
倒数第 k+1 个区间左端点 < 右端点 <l；
其余区间任选。
有计算式
k⋅lk−1_⋅(2N−l)k_⋅(l+1−k2)⋅2−(N−k−1)(2N−2k−1)!
化简可以得到
l!(2N−l)!k2−(N−k)(2N−2k−1l−k−1)
定义
fl,s,t=N−1∑k=1ks2k(2N−2k−tl−k−1)(s,t∈{0,1})
则 fl+1,∗,∗ 容易从 fl,∗,∗ 递推得到。
还要考虑没有 k 的情况，考虑先枚举 a0 再分配左右端点，容易数出这样的 a 有 (2N+1)(N!)2 种。
E - Exponent of PI
简要题意.
给定两两互质的正整数 A,B,C，记 Nk 是集合 {n∣n=xBCyCAzAB∧x,y,z∈Z+} 中第 k 小的元素。
则可以证明 ∑k≥11N2k 是 pqπe 的形式，其中 p,e 是整数，q 是正整数。求出 pq 在模 998244353 意义下的结果和 e。
1≤A,B,C≤250。
记集合 I={i∣i=BCu+CAv+ABw∧u,v,w∈N}，则答案为 ∏p∑i∈Ip−2i。
考虑先求出 GF F(x)=∑i∈Ixi，再考虑把它改成 DGF。记方案数的 GF 是
G(x)=1(1−xBC)(1−xCA)(1−xAB)
考虑 imodABC 可以确定 umodA,vmodB,wmodC，因此 0,…,ABC−1 内的合法的数的 GF 是
(1−xABC)3(1−xBC)(1−xCA)(1−xAB)
而 F(x) 就是其除一个 1−xABC，即
F(x)=(1−xABC)2(1−xBC)(1−xCA)(1−xAB)
因此 DGF 就是
ζ(2BC)ζ(2CA)ζ(2AB)ζ(2ABC)2
查阅 Wikipedia 可以知道
ζ(2n)=(−1)n+1B2n(2π)2n2(2n)!
其中 B2n 是 Bernouli Number 的第 2n 项。使用载谭 Binomial Sum 求解即可。
H - How to Pose Such a Problem
简要题意.
给定 N 和 4×4 的矩阵 W0…3,0…3，保证 W0,0=0。
从 (0,0) 开始，每一步可以走 (i,j) (0≤i,j≤3)，权值是 Wi,j。一条路径的权值是每一步的权值之积。
对于 k=1,2,…,N，求出走到 (k,k) 且不触碰直线 y=x−1 的路径的权值之和。2≤N≤2.5×105，Wi,j 随机。
令 F(x,y)=∑0≤i,j≤3Wi,jxiyj。
令 gk 是从 (0,0) 走到 (k,k) 且中途不触碰 y=x 的权值和，G(x) 是其 OGF，则答案就是 11−G(x)。
不妨把一步 (i,j) 看成 i 个 +1 和 j 个 −1，那么不触碰直线 y=x−1 的所有路径的所有本质不同的循环移位，和任意游走的路径的所有本质不同的循环移位，的集合相等（懒得组织语言了，读者可以结合代数部分理解）。
计数本质不同的无限制游走的循环移位，只需要考虑把当前在最开头那一步看成第一步，则答案为
[xkyk]∑0≤i,j≤3(i+j)Wi,jxiyj1−F(x,y)
二元有理 GF 的对角线是 D-Finite 的。可以暴力高斯消元。
而有限制游走的循环移位，则考虑将第一个 G(x) 的结构循环移位，即
[xk]∑j≥12j⋅gjxj1−G(x)=[xk]2xG′(x)1−G(x)
则我们现在有 H(x)=xG′(x)1−G(x)，要求 11−G(x)。容易解得 11−G(x)=exp(∫x0t−1H(t)dt)。