TPGA - The Permutation Game Again
Since YoMamaSoFat was able to answer Blackhood's and Kira's question as in TPGAME (though with a little help from your side), it was my turn to ask him a question. This would again be a coding question as you might be knowing he is a noob in coding. I gave him a permutation of N distinct integers from 1...N and asked him the rank of the permutation when all possible permutations of the integers are arranged lexicographically. For example, for N = 3, all possible permutations arranged lexicographically would be:-
- 1 2 3
- 1 3 2
- 2 1 3
- 2 3 1
- 3 1 2
- 3 2 1
From the above, rank of 1 2 3 would be 1, rank of 1 3 2 would be 2 and so on.
HELP HIM!
NOTE:- You may assume it is the same permutation which Blackhood gave him in TPGAME to tell the number of inversions for each integer in it.
Input
First line of the input contains t, the number of test cases (1 <= t <= 10). 2 * t lines follow, two for each test case. Each test case begins with an integer N, the number of elements in the permutation (1 <= N <= 200000). The next line contains N space separated distinct integers from 1...N, representing the permutation.
Output
For each test case, print the rank of permutation %1000000007 on a new line.
Example
Input: 3 1 1 3 3 2 1 4 2 1 4 3 Output: 1 6 8
hide comments
miamimagna:
2024-11-03 19:43:22
less go first try passed using bit... my 2 cents for everyone would be try to keep precomputed factorial!!!! and use long long with fast io |
|
depressedboy:
2022-01-20 14:47:42
USE BIT
|
|
kshubham02:
2019-08-24 21:26:48
Time limit too strict.
|
|
eulerkochy:
2018-12-14 06:09:24
O(nlogn) works fine..little bit combi+ BIT ! |
|
akjol2049:
2018-12-05 06:26:53
NlogN TL.. does O(N) solution exist? |
|
jmr99:
2018-07-19 17:51:39
getting wrong answer again and again !! |
|
be1035016:
2018-06-25 22:24:12
BaZ Pro;) |
|
vijayrit:
2017-07-04 19:56:01
i am getting TLE ;-( Please help
|
Added by: | null |
Date: | 2017-07-03 |
Time limit: | 0.100s-1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |
Resource: | Motivated by www.spoj.com/problems/PERMRANK |