← 返回题目列表

AtCoder · agc030_d

D. 求和求逆

中文机器翻译题面 查看原题

分数: 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