题解：Luogu P10004 [集训队互测 2023] Permutation Counting 2

题意

给定 \(n\)，对于所有 \(0\leq x,y<n\) 求有多少长度为 \(n\) 的排列 \(p\) 满足 \(\sum\limits_{i=1}^{n-1}[p_i<p_{i+1}]=x\) 且 \(\sum\limits_{i=1}^{n-1}[p^{-1}_i<p^{-1}_{i+1}]=y\)，答案对给定的质数模数 \(MOD\) 取模。\(1\leq n\leq 500\)。

题解

半年前做的题了，补一下题解。

很神仙的计数题。

我们先考虑只有 \(p\) 的限制怎么做。考虑二项式反演，钦定 \(p\) 中有 \(x\) 个相邻上升对，相当于钦定 \(p\) 中有 \(n-1-x\) 个相邻下降对，而每个下降对可以视作新开一个连续上升段，所以这还相当于钦定原序列被分为 \(n-x\) 个上升段。可以发现，这等价于把 \(1,2,\cdots,n\) 划分成 \(n-x\) 个标号集合，于是方案数即为 \(\displaystyle{n\brace n-x}(n-x)!\)。套反演就可以计算答案。

回到原题，上面的做法启发我们做二元二项式反演。令 \(F_{i,j}\) 表示 \(p\) 中恰好有 \(i\) 个上升对、\(p^{-1}\) 中恰好有 \(j\) 个上升对的方案数，\(G_{i,j}\) 表示钦定 \(p\) 中有 \(i\) 个上升对、\(p^{-1}\) 中有 \(j\) 个上升对的方案数。根据二项式反演，

\[F_{i,j}=\sum_{x=i}^{n-1}(-1)^{x-i}\binom{x}{i}\sum_{y=j}^{n-1}(-1)^{y-j}\binom{y}{j}G_{i,j} \]

考虑如何计算 \(G_{i,j}\)。不妨尝试刻画 \(p^{-1}\) 中的 \(n-j\) 个上升段在 \(p\) 中表现为什么，根据定义，\(p^{-1}\) 中的一个上升段 \([l,r]\) 表示 \(p\) 中 \(l,l+1,\cdots,r\) 的出现位置是单调递增的。接下来是很精妙的一步：对于 \(p^{-1}\) 中的每个上升段 \([l,r]\)，我们考虑把 \(l,l+1,\cdots,r\) 依次插入 \(p\) 的 \(n-i\) 个上升段中，并且我们只关心每个 \(p\) 的上升段中插入了多少个元素。我们发现这样确定了一种插入方案后，构成 \(p\) 的每个上升段的数集就确定了，那么自然 \(p\) 也就被确定了。而我们也不难通过一个确定的 \(p\) 反推插入方案，所以我们构造的映射是一种双射关系。

进一步地，我们把这个双射放到矩阵上考虑：用 \(a_{x,y}\) 表示 \(p^{-1}\) 的第 \(y\) 个上升段中有多少数插入到了 \(p\) 的第 \(x\) 个上升段中。那么问题转化为给 \((n-i)\times (n-j)\) 的矩阵的每个格子上填非负整数，满足每行的和以及每列的和为正数，且填的数的总和为 \(n\)，求方案数。

设 \(f_{i,j}\) 为 \(i\times j\) 的矩阵的答案。我们再次套用二元二项式反演，设 \(g_{i,j}\) 表示 \(i\times j\) 的矩阵，只满足填的数非负且总和为 \(n\) 这个条件的方案数，插板可以得到 \(g_{i,j}=\dbinom{n+ij-1}{ij-1}\)。考虑枚举矩阵恰好有 \(i-x\) 行和 \(j-y\) 列的和为 \(0\)，那么可以得到

\[g_{i,j}=\sum_{x=0}^{i}\binom{i}{x}\sum_{y=0}^{j}\binom{j}{y}f_{x,y} \]

因此可以反演回去：

\[f_{i,j}=\sum_{x=0}^{i}\binom{i}{x}(-1)^{i-x}\sum_{y=0}^j\binom{j}{y}(-1)^{j-y}g_{x,y} \]

显然 \(G_{i,j}=f_{n-i,n-j}\)，这样我们就可以反演回去得到答案了！

直接做二元二项式反演是 \(\mathcal{O}(n^4)\) 的，需要优化。考虑分步卷积。以 \(f_{i,j}\) 为例，我们注意到第二个 \(\sum\) 内的式子只和 \(j,x\) 有关，我们 \(\mathcal{O}(n^3)\) 预处理 \(s_{j,x}=\sum\limits_{y=0}^j\binom{j}{y}(-1)^{j-y}g_{x,y}\)，这样 \(f_{i,j}=\sum\limits_{x=0}^{i}\binom{i}{x}(-1)^{i-x}s_{j,x}\) 就同样可以 \(\mathcal{O}(n^3)\) 计算了。

时间复杂度 \(\mathcal{O}(n^3)\)。轻度卡常，可以 \(\mathcal{O}(n^2)\) 预处理组合数减少取模次数。