030D

Problem StatementYou are given an integer sequence of length $N$: $A_1,A_2,...,A_N$. Let us perform $Q$ operations in order. The $i$-th operation is d ......

# AT_agc030_d [AGC030D] Inversion Sum 题解 ## 题目大意 给你一个长度为 $n$ 的数列，然后给你 $q$ 次交换操作，你每次可以选择操作或者不操作，问所有情况下逆序对的总和。（$n, q \le 3000$） ## 分析 很容易想到 $dp$，但是发现不好直 ......

### 题目大意 一个长度为 $n$ 的数列，然后给你 $q$ 个交换或不交换操作，你可以选择操作或者不操作，问所有情况下逆序对的总和。 答案需要对 $10 ^ 9 + 7$ 取模。 （$n\leq 3000$，$q\leq 3000$）。 ### 思路 这道题非常巧妙。 我们先考虑转化题意，求逆序 ......

## 题意 给定一个长度为 $n$ 的排列 $a$ 和 $m$ 个形如 $\left(x,y\right)$ 的操作，每次操作可以选择是否交换 $a_x, a_y$，求最终所有形成的排列的逆序对总数。 （$1 \le n,m \le 3000$）。 ## 题解 考虑转化题意，考虑求出最终总的期望逆序 ......