The 2023 ICPC Asia Xi'an Regional Contest (The 3rd Universal Cup. Stage 9: Xi'an)

xiezheyuan2025/6/19约 3121 字大约 16 分钟

The 2023 ICPC Asia Xi'an Regional Contest
The 3rd Universal Cup. Stage 9: Xi'an
Osijek Competitive Programming Camp Fall 2024. Day 8. Xi'an Contest
Link

#	Problem	Coding Status	Document Status
A	An Easy Geometry Problem	Accepted	Finished
B	Counting Multisets	Planned	Unavailable
C	Counting Strings	Accepted	Finished
D	Bracket Sequence	Attempted	Unavailable
E	Dominating Point	Accepted	Planned
F	An Easy Counting Problem	Accepted	Finished
G	An Easy Math Problem	Accepted	Finished
H	Elimination Series Once More	Accepted	Planned
I	Max GCD	Accepted	Finished
J	Graph Changing	Planned	Unavailable
K	Penguins in Refrigerator	Planned	Unavailable
L	Prism Palace	Accepted	Planned
M	Random Variables	Accepted	Finished
N	Python Program	Ignored	Ignored

A. An Easy Geometry Problem

给定一个长度为 $n$ 的序列 $a$ 和一个一次函数 $F(x)=Kx+B$ 。有 $q$ 次操作，支持：
1 l r v $\forall i\in[l,r],a_i\gets a_i+v$ 。
2 l r 对于 $i$ ，定义半径 $r$ 是好的，当且仅当：
$i+r\leq n,i-r\geq 1$ 。
$\forall k\in[1, r],A_{i+k}-A_{i-k}=F(k)$ 。
你需要找出最大的好的 $r$ 。
$1\leq n,q\leq 2\times 10^5$ ，时间限制 $5000\mathrm{ms}$ 。

Difficulty：Medium (simple math, hash, segment tree).

首先询问中的好的 $r$ 一定是单调的，因此我们可以先二分，改为判定性问题。

第一条限制是简单的，关键在于第二条式子，我们尝试给约束凑一个好一点的形式：

\begin{aligned} A_{i+k}-A_{i-k}&=Kk+B\\ A_{i+k}-A_{i-k}&=\frac{K}{2}((i+k)-(i-k))+B\\ A_{i+k}-\frac{K}{2}(i+k)&=A_{i-k}-\frac{K}{2}(i-k)+B\\ 2A_{i+k}-K(i+k)&=2A_{i-k}-K(i-k)+2B\\ \end{aligned}

那么我们可以令 $f_i=2A_i-Ki,g_i=2A_i-Ki+2B$ ，如果要验证 $r$ 是否可行，相当于验证 $f[i+1,i+r]$ 是否与 $\mathrm{reverse}(g[i-r,i-1])$ 相等。

可以将 $g$ 倒序维护来消去 $\mathrm{reverse}$ ，然后逐个比较显然是不行的，换成 Hash 即可。我们还需要支持区间加，线段树简单维护一下即可。时间复杂度 $O(n\log^2 n)$ ，Submission。

C. Counting Strings

给定一个长度为 $n$ 的仅由小写英文字母组成的字符串 $S$ ，你需要求出全体满足 $\exists [l,r]\subseteq [1, n],\gcd(l,r)=1\land S[l,r]=T$ 的字符串 $T$ 的长度和。
$1\leq n\leq 10^5$ ，时间限制 $6500\mathrm{ms}$ 。

Difficulty: Hard (SAM, simple number theory, tree theory, bruteforce technology, sqrt decomposition (time complexity balancing)).

ICPC 2023 Xi'an Regional 压轴题。

根据更相减损法，我们将 $\gcd(l,r)$ 换成 $\gcd(r-l,r)$ 。先建出 SAM，然后枚举这个长度加 $1$ 的 $r-l$ ，对于每一个与 $r-l$ 互质的 $r$ ，找到 $S[1,r]$ 在 SAM 上的表示节点 $e_r$ ，如果 $e_r$ 的某一个祖先 $p$ 的长度区间 $[L_p,R_p]$ 满足 $r-l\in [L_p-1,R_p-1]$ ，那么 $(l,r)$ 就是一个答案。注意这样会算重。

可以改为枚举满足 $r-l\in[L_p-1,R_p-1]$ 的 $p$ ，如果 $p$ 的 Endpos 等价类集合中有 $\gcd(r,r-l)=1$ 的 $r$ 就可以造成贡献，根据 SAM 的性质这样不会算重。

但是如果枚举一个 $r-l$ 再枚举一个 $p$ ，时间复杂度太高。考虑要给非常玄学的方法，枚举 $r-l$ 的质因子集合，在枚举集合时若新增一个质数，那么就要删除质数的倍数作为 $r$ 的贡献。如何删除呢？枚举这样的 $r$ ，找到 $e_r$ ，找到 $e_r$ 的一个最浅的祖先 $p$ ，如果 $p$ 的 Endpos 中没被删除的点只有 $r$ 了，那么 $(e_r,p)$ 路径上的所有点就都不再具有贡献，满足 $r-l\in[L_u-1,R_u-1]$ （ $u\in (e_r,p)$ ）的所有 $r-l$ 的贡献就会减去 $1$ ，注意到 SAM 上的一条链的区间是连续的，所以可以合并成一个大区间，这样就只需要做一次区间减了。可以预见到修改与查询之间肯定失衡，因此这个区间加单点查询的数据结构我们不用树状数组，而改用差分 + 分块来平衡时间复杂度。

OK 一个遗留问题是怎样找到这样的 $p$ ，我们找到 $e_r$ 在 DFS 序中相邻的，未被删除的前缀节点，和 $e_r$ 之间做一下 LCA，深度较深的就是 $p$ 的父亲。这个做法看起来就非常对，只是想到不太容易。维护 DFS 序相邻用双向链表就好了，LCA 需要用一个 $O(1)$ 查询的 LCA，这样找 $p$ 就可以优化到 $O(1)$ 。

如果我们在整个流程中删除了 $N$ 次，那么时间复杂度就是 $O(N+n\sqrt{n})$ 。jiangly 提到 $N=\sum_{i=1}^{n-1} [\mu(i)\neq 0]\frac{n}{\max\limits_{p\mid N, p\in \mathbb{P}} p}$ 。通过代码：

n = 10^5
MaxDivisor[x_] := If[x == 1, 1, Last[FactorInteger[x]][[1]]]
Total[Floor[n / MaxDivisor[#]] & /@ Select[Range[n - 1], MoebiusMu[#] != 0 &]]

可以得到 $N=191715737\sim 2\times 10^7$ 是可以接受的。实现较为繁琐，Submission。

F. An Easy Counting Problem

给定 $k,p,x$ ，计算满足下列条件的数对 $(a,b)$ 的数量（答案对 $998,244,353$ 取模）：
$0\leq b\leq a<p^k$ 。
$\binom{a}{b}\equiv x\pmod{p}$ 。
$1\leq k\leq 2^{1000},2\leq p\leq 5000,1\leq x<p,p\in\mathbb{P}$ ， $k$ 以二进制形式给出，时间限制 $6000\mathrm{ms}$ 。

Difficulty: Medium (Lucas theorem, standard number theory, convolution).

这题好套路啊。

题面已经几乎将 Lucas 定理写在脸上了，因此自然考虑 Lucas 定理的模式去做一个数位 dp。

设 $f(i,j)$ 表示考虑到 $a,b$ 在 $p$ 进制下的第 $i$ 位， $\prod\limits_{k=1}^{i} \binom{a_k}{b_k}\equiv j\pmod{p}$ （ $a_k$ 表示 $a$ 在 $p$ 进制下的第 $k$ 位， $b_k$ 类似）。

预先计算一个：

g(k)=\sum_{a=0}^{p-1}\sum_{b=0}^{p-1} \left[\binom{a}{b}\bmod p = k\right]

那么可以立即写出状态转移方程：

f(i,j) = \sum_{xy\bmod p = j} f(i - 1, x) g(y)

做到这里时间复杂度应该是 $O(kp^2)$ ，显然过不了。

注意这个 dp 的形式很像卷积，此处一个非常经典的 trick 是利用 $p$ 是一个质数，我们取 $x,y,j$ 的离散对数（具体地，我们只需要记 $f'(i,j)=f(i,g^j)$ 即可）。这样就变成了 $x+y\bmod p=j$ ，这是循环卷积的形式，做一遍普通卷积然后 $O(p)$ 统计一下即可。

用 NTT 做卷积，做到这里时间复杂度应该是 $O(p^2+kp\log p)$ ，显然还是过不了。

注意到卷积是有结合律的，所以可以用快速幂去优化（由于 $k$ 给出的是二进制形式，所以很方便），时间复杂度 $O(p^2+p\log p\log k)$ ，Submission。

G. An Easy Math Problem

给定 $n$ ，对于所有的 $p\leq q,pq\mid n$ ，计算本质不同的 $r=\frac{p}{q}$ 数量。 $T$ 组数据。
$1\leq T\leq 2000,1\leq n\leq 10^{10}$ 。

Difficulty: Easy (number theory).

注意到将 $\frac{p}{q}$ 约分后仍然满足 $pq\mid n$ ，因此我们可以假定 $p,q$ 互质，可以证明这样就不会重复了。

考虑如何计算答案？不妨对 $\frac{p}{q}$ 计数，枚举 $n$ 的每一个质因子 $P$ ，考虑这个质因子放 $p$ 还是放 $q$ 还是不放，如果放的话要放多少个。很容易发现答案就是：

\prod_{p_i^{e_i}\mid n} 2e_i+1

由于本题要求 $p\leq q$ ，所以答案还要加 $1$ 后再除以 $2$ （注意 $p=q=1$ 不会算重复）。

时间复杂度 $O(T\sqrt{n})$ ，Submission。

I. Max GCD

给定一个长度为 $n$ 的序列 $a$ ，有 $q$ 次询问，每次询问给出 $[l,r]$ ，你需要找到最大的 $\gcd(a_x,a_y,a_z)$ ，满足：
$l\leq x<y<z\leq r$ 。
$y-x\leq z-y$ 。
如果不存在，则答案为 $0$ 。
$3\leq n\leq 1.5\times 10^5,1\leq q\leq 10^5,1\leq a_i\leq 10^6$ 。

Difficulty: Medium (number theory, sqrt decomposition (time complexity balancing), sweeping line method).

对于每一个可能的答案 $g$ ，如果数对 $(x,y,z)$ 可能对答案产生贡献，至少要 $g\mid a_x, g\mid a_y, g\mid a_z$ 。由于 $y-x\leq z-y$ 这一限制， $x,y$ 越近越好，所以如果只保留 $g$ 的倍数，那么 $x,y$ 肯定是相邻的。至于 $z$ ，则是满足 $y-x\leq z-y,g\mid a_z$ 的最小的 $z$ 最优（反正我们钦定只造成 $g$ 的贡献，没必要选更后面的，选较小的有利于被询问区间包含）。

考虑经过我们的筛选， $(x,y,z)$ 有多少个？我们可以枚举 $x,g$ ，这样可以得出上界是 $\sum_{k=1}^{n} d(a_k)$ 个，它的上界大概是 $240n\sim 3.6\times 10^7$ （通过那个著名的 $\max d, \max \omega$ 表可以轻松查出 $240$ 这个数值）。可能可以接受。

那么只需要找到这些点，就可以做一个二维数点来回答询问，如果是离线二维数点的话，需要一个数据结构，支持 RMQ 和单点修改（单点取 $a_i\gets \max(a_i,v)$ ）。一般的场合就会用线段树这些，不过本题中询问数与点数严重不平衡，因此可以用 $O(1)-O(\sqrt{n})$ 的分块换掉 $O(\log n)-O(\log n)$ 的线段树。

唯一的问题是如何找到这些 $(x,y,z)$ 。我们枚举 $y$ 和它的因子 $g$ ，找到上一个因子 $x$ ，那么就要满足 $z\geq 2y-x$ ，可以在 $2y-x$ 处挂上 $(x,g)$ ，然后再倒着扫一遍就可以找到最近的 $z$ 。

时间复杂度 $O(n2^{\frac{\log a_i}{\log \log a_i}}+q\sqrt{n})$ （如果你承认 GRH，可以得到这么一个时间复杂度），Submission。

M. Random Variables

给定 $T,p$ ，有 $T$ 次询问，每次询问给出 $n,m$ 。我们将进行 $n$ 次随机试验，每次从 $[1,m]$ 中随机选择一个整数，求众数的出现次数期望乘 $m^n$ 的结果。答案对 $p$ 取模。
$1\leq T\leq 10^4,2\leq p\leq 10^9+7,1\leq n\leq 1000,1\leq m\leq 10^9,1\leq \sum n\leq 10^4$ 。

Difficulty：Medium-Hard (generating function, combinatorics, basic calculus, nontraditional dp optimization).

记 $P(f(M))$ 表示众数出现次数满足 $f$ 的方案数，那么答案可以看成：

\sum_{i=1}^{n} i P(M=i)=nP(M\leq n)-\sum_{i=1}^{n-1} P(M\leq i)

而计算 $P(M\leq i)$ 显然比 $P(M=i)$ 容易一点。这个 $P(M\leq i)$ 有一个非常简单的，基于生成函数公式：

P(M\leq k) = \sum_{\substack{a_1+a_2+\cdots+a_m=n\\ a_1,a_2,\cdots,a_m\leq k}} \genfrac{(}{)}{0pt}{}{n}{a_1\; a_2\;\cdots\; a_m}=\sum_{\substack{a_1+a_2+\cdots+a_m=n\\ a_1,a_2,\cdots,a_m\leq k}} \frac{n!}{a_1!a_2!\cdots a_m!}=n!\cdot [z^n]\left(\sum_{i=0}^{k} \frac{z^i}{i!}\right)^m

如果 $p=998,244,353$ 的话我们就可以直接多项式 ln / exp 之类的去做，但是本题连 $p$ 是质数都没有保证，因此我们需要抛弃多项式做法，转而寻找一些不那么依赖于 $p$ 的方法，比如说递推。

设 $f_k(n,m)$ 表示 $n\gets i$ 时 $P(M\leq m)$ 的结果，先来考察 $\frac{1}{n!}f_k(n, m)$ ，我们令：

A_k(z)=\sum_{i=0}^{k} \frac{z^i}{i!}

那么 $\frac{1}{n!}f_k(n, m)=[z^n] A_k^m(z)$ 。

考察 $A_k'(z)$ ：

\begin{aligned} &A_k'(z)=\sum_{i=0}^{k} \frac{iz^{i-1}}{i!}=\sum_{i=0}^{k-1} \frac{z^i}{i!}=A_{k}(z)-\frac{z^k}{k!}\\ \implies&\frac{\mathrm{d}}{\mathrm{d}z} A_k^m(z)=mA_k^{m-1}(z)A_k'(z)=mA_k^m(z)-mA_k^{m-1}(z)\frac{z^k}{k!}\\ \implies& [z^n] A_k^{m+1}(z)=[z^n] mA_k^{m}(z)-\frac{m}{k!} [z^{n-k}] A_k^{m-1}(z)\\ \implies& \frac{(n+1)f_k(n+1,m)}{(n+1)!} = m\cdot \frac{f_k(n,m)}{n!}-\frac{m}{k!} \cdot \frac{f_{k}(n-k,m-1)}{(n-k)!}\\ \implies& \frac{f_k(n,m)}{(n-1)!} = m\cdot \frac{f_k(n-1,m)}{(n-1)!}-\frac{m}{k!} \cdot \frac{f_{k}(n-k-1,m-1)}{(n-k-1)!}\\ \implies& f_k(n, m)=mf_k(n-1,m)-m\binom{n-1}{k} f_k(n-k-1,m-1) \end{aligned}

边界 $f_k(0,)=1,f_k(n,0)=[n=0]$ 。

由于组合数可以通过杨辉三角递推 $O(n^2)$ 求得，因此可以不用阶乘逆元的方法，来让 $p$ 不为质数时依然可以求出答案，时间复杂度 $O(n^2m)$ 无法通过。

观察递推式，注意到能对 $f_k(n,m)$ 产生贡献的 $f_k(i,j)$ ，必有 $j\geq m-\frac{n}{k+1}$ ，所以第二维的实际大小是 $O(\frac{n}{k+1})$ 。故通过恰当的实现，可以做到：

O\left(\sum_{i=1}^{n}\frac{n^2}{i+1}\right)=O(n^2\log n)

Submission。