题意
给定 \(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\) 个上升对的方案数。根据二项式反演,
考虑如何计算 \(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}=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)\) 预处理组合数减少取模次数。