资讯详情

要不是前面花了四十分钟手写 bitset，感觉这题还真可能过。下面的东西都是场上推出来的，只不过不可能写完了。

考虑固定操作序列，如何求出 \(i\) 的最终位置？此时每个操作对 \(i\) 形如 \(pos\leq x\) 或者 \(pos\geq x\) 的限制，记录上下界，若在某个时刻上界或下界爆掉了，那么答案就是爆掉的位置。当然还有一些 \(pos=x\) 的限制，先不去管。

枚举 \(i\) 以及最后的位置 \(j\)，对序列倒着计数。称 \(pos\geq x\) 为一类限制，用 \(k1_a\) 代表 \(a\) 位置上有几个一类限制，\(sk1\) 代表一类限制的前缀和，\(hk1\) 代表一类限制的后缀和，二类限制同理。记 \(sl\) 为 \(pos=x\) 限制的数量。不妨设下界爆掉了，第一次取到这个下界的时候是 \(p_1\)，爆掉的时候是 \(p_2\)（\(p_1<p_2\)），可以直接写出方案数：

\[A\binom{q-p_2}{hk1_{j+1}+sk2_j-1+sl}\times k1_j\times sk2_j\times A\binom{p_2-p_2}{k1_{j-1}}\times(sk1_{j-1}+hk2_{j+1})! \]

这个式子的唯一难点在于计算两个排列数，不妨设 \(f(a,b)\) 代表 \(\sum\limits_{p1,p2}A\binom{q-p_2}aA\binom{p_2-p_1}b\)，如果能预处理这个东西就可以 \(O(1)\) 计算上面的式子。好像组合意义不太好找，先做一些外部的工作：

\[f(a,b)=\sum\limits_{p_2=1}^qA\binom{q-p_2}a\sum\limits_{i=1}^{p_2-1}A\binom{i}b \]

后面的 \(\sum\) 是排列数上指标求和，找一下组合意义得到 \(\frac{A\binom{p_2}{b+1}}{b+1}\)，具体就是从 \(p_2\) 个位置中放上 \(b\) 个有标号的球，枚举第 \(b\) 个球放在 \(i+1\)。此时式子为：

\[f(a,b)=\sum\limits_{p_2=1}^q\frac{A\binom{q-p_2}aA\binom{p_2}{b+1}}{b+1} \]

\(\frac{1}{b+1}\) 可以扔到外面，对分子找组合意义。类似地，有 \(q+1\) 个位置需要放上 \(a+b+2\) 个有标号的球，枚举一下第 \(b+2\) 个放在 \(p_2+1\) 处，得到 \(\frac{A\binom{q+1}{a+b+2}}{(a+b+2)\binom{a+b+1}{b+1}}\)，注意前面不带 \(A\) 的是组合数。所以最终：

\[f(a,b)=\frac{A\binom{q+1}{a+b+2}}{(a+b+2)\binom{a+b+1}{b+1}(b+1)} \]

\(O(n^2)\) 处理出这个东西后开始分类讨论，上面已经说过了第二类限制使得第一类爆掉的情况，方案数为：

\[f(hk1_{j+1}+sk2_j-1+sl,k1_{j}-1)\times k1_j\times sk2_j\times(sk1_{j-1}+hk2_{j+1})! \]

不妨将 \(pos=x\) 称为第三类限制，统计第三类限制使得第一类爆掉的情况，\(k3\)、\(sk3\)、\(hk3\) 的定义同上：

\[f(hk1_{j+1}+sk2_j+sl-1,k1_j-1)\times k1_j\times sk3_j\times(sk1_{j-1}+hk2_{j+1})! \]

第一类限制使得第二类爆掉的方案数：

\[f(sk2_{j-1}+hk1_j+sl-1,k2_j-1)\times k2_j\times hk1_j\times(sk1_{j-1}+hk2_{j+1})! \]

第三类限制使得第二类爆掉的方案数：

\[f(sk2_{j-1}+hk1_j+sl-1,k2_j-1)\times k2_j\times hk3_j\times(sk1_{j-1}+hk2_{j+1})! \]

考虑第三类爆掉是什么意思，设当前上下界为 \((l,r)\)，若出现 \(pos=x\) 的限制，且 \(l<x<r\)，那么这就爆了：

\[A\binom{q-p_1}{sk2_j+hk1_j+sl-1}\times k3_j\times(sk1_{j-1}+hk2_{j+1})! \]

里面有个枚举 \(p_1\)，不过很容易消去，直接考虑组合意义得到 \(\frac{A\binom{q}{sk2_j+hk1_j+sl-1}}{sk2_j+hk1_j+sl-1}\)。

当 \(sl=0\) 时，注意还有初始位置的限制。直接考虑两类限制中最严的，如果没爆掉就让其爆掉。注意到并不能枚举 \(j\)，不过显然最终的位置只可能有 \(O(q)\) 个，枚举这些位置即可。

时间复杂度 \(O(nq)\)，帅！