[AGC023E] Inversions
题意翻译
给定一个长度为 $n$ 的序列 $A$,问所有满足 $\forall i,P_i\le A_i$ 的 $1\sim n$ 的排列的逆序数的和为多少。
答案对 $10^9+7$ 取模。
题目描述
[problemUrl]: https://atcoder.jp/contests/agc023/tasks/agc023_e
すぬけ君は、長さ $ N $ の整数列 $ A $ を持っています。 すぬけ君は、$ (1,\ 2,\ ...,\ N) $ の順列 $ P $ であって、次の条件を満たすものが好きです。
- 全ての $ i $ ( $ 1\ \leq\ i\ \leq\ N $ ) について、$ P_i\ \leq\ A_i $
すぬけ君は、条件を満たすような順列の転倒数 ( ※ ) に興味を持ちました。 すぬけ君のために、条件を満たすような全ての順列について転倒数を求め、その総和を求めてください。 ただし、答えは非常に大きくなることがあるので、$ 10^9\ +\ 7 $ で割った余りを求めてください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ A_1 $ $ A_2 $ $ ... $ $ A_N $
输出格式
条件を満たすすべての順列の転倒数の総和を $ 10^9\ +\ 7 $ で割った余りを出力せよ。
输入输出样例
输入样例 #1
3
2 3 3
输出样例 #1
4
输入样例 #2
6
4 2 5 1 6 3
输出样例 #2
7
输入样例 #3
5
4 4 4 4 4
输出样例 #3
0
输入样例 #4
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 19 28 27 18 23
输出样例 #4
848414012
说明
### 注釈
ある長さ $ N $ の数列 $ Z $ の転倒数とは、整数 $ i,\ j $ ( $ 1\ \leq\ i\ <\ j\ \leq\ N $ ) の組であって、$ Z_i\ >\ Z_j $ を満たすものの個数を意味します。
### 制約
- $ 1\ \leq\ N\ \leq\ 2\ \times\ 10^5 $
- $ 1\ \leq\ A_i\ \leq\ N $ ( $ 1\ \leq\ i\ \leq\ N $ )
- 入力はすべて整数である。
### Sample Explanation 1
条件を満たす順列は $ (1,2,3) $, $ (1,3,2) $, $ (2,1,3) $, $ (2,3,1) $ の $ 4 $ つです。 それぞれの転倒数は $ 0 $, $ 1 $, $ 1 $, $ 2 $ なので、その総和である $ 4 $ を出力します。
### Sample Explanation 2
条件を満たす順列は $ (4,2,5,1,6,3) $ のみです。 この順列の転倒数は $ 7 $ なので、$ 7 $ を出力します。
### Sample Explanation 3
条件を満たす順列は $ 1 $ つもありません。