当前位置: 首页 > news >正文

题解: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)\) 预处理组合数减少取模次数。

http://www.hskmm.com/?act=detail&tid=35339

相关文章:

  • 题解:Luogu P2075 区间 LIS
  • 英语_阅读_2050 Space tourism_待读
  • goframe框架命令行工具gf在zsh下不能用
  • 题解:Luogu P4143 采集矿石
  • 从18w到1600w播放量,我的一点思考。
  • 扣一个细节问题
  • 10.20java作业
  • 题解:Luogu P14175 【MX-X23-T5】向死存魏
  • 题解:Luogu P14254 分割(divide)
  • 题解:Luogu P6898 [ICPC 2014 WF] Metal Processing Plant
  • 20251020
  • 32-腾讯IM接入资料和定价
  • 题解:AtCoder ARC207A Affinity for Artifacts
  • 构造单
  • [笔记]高斯消元
  • 半导体设备各细分领域的国内外龙头公司
  • CSP-S 34
  • 02.Python百行代码实现抽奖系统
  • CSP-S 35
  • CSP-S 29
  • 2025网络安全振兴杯wp
  • 10.20每日总结
  • CSP-S 31
  • 后缀树
  • ES原理、zookeeper、kafka
  • CF1606E Arena 题解(动态规划)
  • 服务器CPU市场概况2025
  • CSP-S 24
  • 读书笔记:深入理解java虚拟机
  • CSP-S 19