Sad Cuts
Practice
4 (4 votes)
Algorithms
Combinatorics
Fast fourier transform
Hard
Problem
59% Success 1124 Attempts 50 Points 6s Time Limit 512MB Memory 1024 KB Max Code

Are you sad ? Don't be, unlike me

You are given a sad array $$A$$ of size $$N$$ and an additional sad integer $$K$$. Now, we create a new sad array $$B$$, of size $$N \cdot K $$, where $$B[i] = A[i]$$, for $$ 0 \le i \le N-1 $$ and $$B[i]=B[i-N]$$ for $$ N \le i \le (N \cdot K) -1 $$.

Now, we define an inversion to be a pair of indices $$(E1,E2)$$ lying in the same subsequence $$S$$, such that $$ E1 < E2 $$, but $$ B[E1] > B[E2] $$

Now, you need to cut this sad array $$B$$ into any number of sad non-empty non-intersecting subsequences. Each element from the given array should belong to exactly one of the subsequences. Let the array be cut into the set of subsequences $$  \{ S_0, S_1, ...S_{k-1} \} $$. Let $$Z$$ be the sum of the number of inversions in each individual subsequence.

You know what's next right? Considering the array can be cut into each distinct set of subsequences with equal probability, you need to find the Expected Value of $$Z$$. What this means is that let the array be cut into the set of subsequences $$ \{ S_0,S_1..S_{k-1} \} $$ or into subsequences $$ \{ C_0,C_1..C_{l-1} \} $$, where $$ S \ne C $$. The probability of array being in state $$S$$ or in state $$C$$ is equal to the probability of the array being cut into any other set of subsequences.

Let the answer be an irreducible fraction $$P / Q $$. You need to print $$P \cdot Q^{-1} $$ Modulo a given prime number $$M$$. It is guaranteed, that for all of the given tests, $$ Q \not\equiv 0 $$ Modulo $$M$$. So, the answer will always exist and is unique for the given test-set, since $$M$$ is prime.

Input Format:

The first line contains $$3$$ space separated integers $$N$$, $$K$$ and $$M$$. The next line contains $$N$$ space-separated integers, where the $$i^{th}$$ integer denotes $$A[i]$$.

Output Format:

Print the given answer on a single line

Constraints :

$$ 1 \le N \le 2000 $$

$$ 1 \le A[i] \le 10^9 $$

$$ 1 \le K \le 10^{10}$$

$$ 3 \le M \le 5 \cdot 10^4 $$

$$M$$ is a prime number

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:20
114 votes
Tags:
ApprovedEasyOpenPriority queueTrees
Points:50
8 votes
Tags:
AlgorithmsBinomial CoefficientsEulerian numberFast Fourier transformGenerating FunctionsHardStirling Numbers
Points:50
6 votes
Tags:
Permutation and combinationDynamic Programming2D dynamic programmingFast Fourier transformAdvanced AlgorithmsAlgorithmsDivide-and-conquer algorithm