题解：AT_arc186_d [ARC186D] Polish Mania
xyz105
·
·
题解
\begin{Bmatrix}\color{red}\LARGE\bold{Solution}\\\normalsize\texttt{No.015 }\bold{AT\_arc186\_d}\end{Bmatrix}\times\footnotesize\texttt{ By Xyz105}
题目描述
Polish 数列的递归定义如下：
- 对于一个所有元素非负的非空数列 (V_1,V_2,\ldots,V_M)，如果该数列为 Polish 数列，当且仅当存在 V_1 个其它的 Polish 数列 W_1,W_2,\ldots,W_{V_1}，满足将 (V_1) 和 W_1,W_2,\ldots,W_{V_1} 连接起来后得到的新数列与 (V_1,V_2,\ldots,V_M) 相等。
特别地，规定 (0) 是 Polish 数列。
由此可推得，(1,0),(2,0,0),(3,0,1,0,0) 等都是 Polish 数列。
现给定一个长度为 N 的数列 A（其所有元素 (A_1,A_2,\ldots,A_N) 均非负），试求出长度为 N 且字典序不大于 A 的 Polish 数列个数。对 998244353 取模。
（本翻译已提交至对应 Luogu 题目界面）
解题思路
格路计数转化 + 反射容斥。一定程度上参考了 官方题解。
观察数列 A 如果是 Polish 的，它应该满足什么性质：
-
- 不存在 i\isin [1,n-1] 使得 \sum_{j=1}^i a_j\le i-1。
通过后续的分析，可以发现 (2.) 这个条件实际上就是“不存在 i\isin [1,n-1] 使得 \sum_{j=1}^i a_j=i-1”。
考虑将其转化成如下格路问题：
初始位置为 (0,1)。然后循环枚举 i\isin [1,n]，对于每一个 i，先向 y 轴正方向移动 a_i 格，再向 x 轴正方向移动 1 格。限制如下：
- 最终目的地一定是 (n,n)。
- 沿途不能经过 (1,1),(2,2),\ldots,(n-1,n-1) 这些点。
（推论：点 (n,n) 一定是从 (n-1,n) 移动过来的，因为显然 a_n=0）
问题变为计算满足上述条件的路径方案数。
因为有字典序要求，所以考虑题目给定的数列 A 要怎么用。假设 B 是一个长度为 N 且字典序不大于 A 的 Polish 数列。
枚举 i\isin [1,n]，分别计算当 B 的前缀为 (A_1,A_2,\ldots,A_{i-1},b) 时满足条件的 B 的个数，其中 0\le b<A_i。
设 x=i,y=1+(\sum_{j=1}^{i-1}A_j)+b，那么将 (x,y) 走到 (n,n) 且满足上述限制的路径数计入答案。
记 f_{x1,y1,x2,y2} 为从 (x1,y1) 无视限制地走到 (x2,y2) 的方案数 (x1\le x2,y1\le y2)，那么有 f_{x1,y1,x2,y2}=\binom{x2-x1+y2-y1}{x2-x1}。
由 反射容斥 的思想可得，若考虑上述限制，则方案数为 f_{x,y,n-1,n}-f_{y,x,n-1,n}。
容易发现当 i 递增时，y 是单调不降的。因此当 y>n 时退出循环即可（x\ge y 的情况也要排除）。时间复杂度 O(n)。
最后别忘记判断 A 本身是否也是 Polish 数列。
参考代码
Submission on Atcoder。