题解 AT4513 【[AGC030D] Inversion Sum】

小粉兔 · 2020-03-10 16:19:04 · 题解

因为 N 很小，考虑直接枚举位置对 \langle i, j \rangle（1 \le i < j \le N）以统计逆序对。

考虑一个概率 DP：令 f(i, j)（1 \le i, j \le N）为当前时刻下，A_i > A_j 的概率。
（这里假设对于 Q 个操作，每个操作都以 1 / 2 的概率执行）

那么最终时刻下，满足 i < j 的 f(i, j) 之和，再乘以 2^Q 就是答案（期望的线性性）。

按顺序考虑每个时刻（操作），考虑新的 f(i, j) 和原先的比有什么变化。

可以发现只有 \mathcal O (N) 个位置会发生变化。具体地说，只有 i, j 有至少一个等于 X_i 或 Y_i 时才有可能发生变化。

暴力转移即可。

时间复杂度为 \mathcal O (N (N + Q))，评测链接。