ABC309G Ban Permutation 题解
前置知识
- 二项式反演(以后会补上笔记的!)
- 状压 DP
符号约定
\(\lor\) 为逻辑或,相当于 C++ 中的 |
运算符。
题意简化
求 \(n\) 的排列 \(P\) 的方案数,要求 \(\lvert P_i - i \rvert \geqslant X\)。
分析
排列问题有点抽象,于是有套路:把一个排列看成 \(n\times n\) 的棋盘上放车的方案——数字 \(p_i\) 在 \(i\) 的位置上,相当于棋盘的 \((i,p_i)\) 位置放了一个车。显然 \(i,p_i\) 都不会重复,所以正确。
然后发现是个计数题,给出了不合法的条件,而且条件与位置相关,往二项式反演方向思考。
按照套路,设 \(g_i\) 为钦定 \(i\) 个数不合法,其他随便排的方案数,\(f_i\) 为恰好 \(i\) 个数不合法的方案数。发现每个 \(g_i\) 包含 \(f_j,j\in[i,n]\),然后每次选择不同的 \(i\) 个数进行钦定,所以一个 \(f_j\) 要算 \(\binom ji\) 次。于是有:
\[ g_i=\sum_{j=i}^n f_i \binom ji \]
脸上都写上二项式反演这五个字了,套一下式子,有:
\[ f_i = \sum_{j=i}^n(-1)^{j-i}\binom ji g_j \]
答案即为:
\[ \begin{aligned} ans &= f_0 \newline &= \sum_{j=0}^n(-1)^{j-0}\binom j0 g_j \newline &= \sum_{j=0}^n(-1)^j g_j \end{aligned} \]
考虑怎么求 \(g_i\)。
回过头来看不合法的条件:\(\lvert P_i - i \rvert < X\),转化为 \(P_i\) 这个棋子不能放在 \([i-X+1,i+X-1]\) 这些横行上。
发现 \(X\leqslant 5\),非常小,也许可以状压?结合上面的转化,如果要状压的话,状态可以直接表示 \([i-X+1,i+X-1]\) 中不合法棋子的集合。
然后 DP 状态设计就有了(这里我们开出来一个新的 \(f\) 数组):\(f_{i,j,s}\) 表示棋盘前 \(i\) 行,放了 \(j\) 个不合法棋子,状态为 \(s\) 的方案数量。
怎么转移?假设当前是 \(f_{i,j,s}\),然后分类讨论:
- 不放新的不合法棋子。 发现这种情况下转移到 \(i+1\) 时,新状态就是 \(s\) 右移一位,即 \(2^{-1}s\)。 为了方便,我们设这个状态为 \(ns\),表示什么都不放时转移到 \(i+1\) 时的状态。 转移方程也就简单了:\(f_{i,j,ns} \gets (f_{i,j,ns}+f_{i,j,s})\)
- 放新的不合法棋子。 可以枚举一下这个不合法棋子能放到的位置(就是 \([i-X+1,i+X-1]\) 区间的空位),直接转移即可。但是注意,当前要做的是向后转移,所以应当枚举的是 \(ns\) 这个状态的空位。假设 \(p\) 是一个空位,则有转移方程:\(f_{i,j,(ns\lor 2^p)} \gets (f_{i,j,(ns\lor 2^p)}+f_{i,j,s})\)。
对于 \(g_i\),由于是钦定了 \(i\) 个位置不合法,其他位置随便排,所以我们对 \(f_{n,i,s}\) 枚举 \(s\) 求和之后,还要乘一个 \((n-i)!\) 满足“剩下位置随便排列”的要求。
按照前面 \(ans\) 的式子求和即可。
时间复杂度 \(\operatorname\Theta(4^Xn^2)\)。
Code:
1 | use std::io; |