分数: 1000 点
问题陈述
给定一个长度为的整数序列 N: A_1,A_2,...,A_N。让我们表演一下 Q 操作按顺序进行。 的 i-th 操作由两个整数描述 X_i 和 Y_i。在此操作中,我们将选择以下两个操作之一并执行它:
- 交换以下值 A_{X_i} 和 A_{Y_i}
- 不执行任何操作
有 2^Q 执行这些操作的方法。求所有这些执行运算的方式的最终序列的反转数之和,模 10^9+7.
这里,序列的反转数 P_1,P_2,...,P_M 是整数对的数量 (i,j) 这样 1\leq i < j\leq M 和 P_i > P_j.
约束
- 1 \leq N \leq 3000
- 0 \leq Q \leq 3000
- 0 \leq A_i \leq 10^9(1\leq i\leq N)
- 1 \leq X_i,Y_i \leq N(1\leq i\leq Q)
- X_i\neq Y_i(1\leq i\leq Q)
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N Q A_1 : A_N X_1 Y_1 : X_Q Y_Q
输出
打印最终序列的反转数的总和,模 10^9+7.
示例输入 1
3 2 1 2 3 1 2 1 3
示例输出 1
6
有四种操作方式,如下:
- 在第一次和第二次操作中都不执行任何操作。最终的顺序是 1,2,3,反转数为 0.
- 在第一个操作中不执行任何操作,然后在第二个操作中执行交换。最终的顺序是 3,2,1,反转数为 3.
- 在第一个操作中执行交换,然后在第二个操作中不执行任何操作。最终的顺序是 2,1,3,反转数为 1.
- 在第一次和第二次操作中执行交换。最终的顺序是 3,1,2,反转数为 2.
这些反转数的总和, 0+3+1+2=6,应打印。
示例输入 2
5 3 3 2 3 1 4 1 5 2 3 4 2
示例输出 2
36
示例输入 3
9 5 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8
示例输出 3
425