#P9534. 逆序数计数

    ID: 6120 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-乘法原理贡献法期望线性性懒标记线段树树状数组逆元线性递推

逆序数计数

题目描述

给定长度为 nn 的整数序列 AA。对每个由 1,2,…,n1,2,\ldots,n 组成且满足 Pi≤AiP_i\le A_i 的排列 PP,计算其逆序数。求所有满足条件的排列的逆序数之和,对 109+710^9+7 取模。

排列的逆序数是满足 i<ji<j 且 Pi>PjP_i>P_j 的下标对 (i,j)(i,j) 的数量。

输入格式

第一行一个整数 nn。

第二行 nn 个整数 A1,A2,…,AnA_1,A_2,\ldots,A_n。

输出格式

输出一个整数,表示所求的和对 109+710^9+7 取模后的结果。若没有满足条件的排列,输出 00。

数据范围

1≤n≤2×1051\le n\le2\times10^5,1≤Ai≤n1\le A_i\le n。

3
2 3 3
4
6
4 2 5 1 6 3
7
5
4 4 4 4 4
0
30
22 30 15 20 10 29 11 29 28 11 26 10 18 28 22 5 29 16 24 24 27 10 21 30 29 28 27 18 23
848414012

AtCoder AGC023 E 原题