#P1542E2. Abnormal Permutation Pairs (hard version)
-
ID: 2057
Type: RemoteJudge
4000ms
512MiB
Tried: 0
Accepted: 0
Difficulty: 10
Uploaded By:
Hydro
Tags> Abnormal Permutation Pairs (hard version)
Description
This is the hard version of the problem. The only difference between the easy version and the hard version is the constraints on $n$. You can only make hacks if both versions are solved.
A permutation of $1, 2, \ldots, n$ is a sequence of $n$ integers, where each integer from $1$ to $n$ appears exactly once. For example, $[2,3,1,4]$ is a permutation of $1, 2, 3, 4$, but $[1,4,2,2]$ isn't because $2$ appears twice in it.
Recall that the number of inversions in a permutation $a_1, a_2, \ldots, a_n$ is the number of pairs of indices $(i, j)$ such that $i < j$ and $a_i > a_j$.
Let $p$ and $q$ be two permutations of $1, 2, \ldots, n$. Find the number of permutation pairs $(p,q)$ that satisfy the following conditions:
- $p$ is lexicographically smaller than $q$.
- the number of inversions in $p$ is greater than the number of inversions in $q$.
Print the number of such pairs modulo $mod$. Note that $mod$ may not be a prime.
The only line contains two integers $n$ and $mod$ ($1\le n\le 500$, $1\le mod\le 10^9$).
Print one integer, which is the answer modulo $mod$.
Input
The only line contains two integers $n$ and $mod$ ($1\le n\le 500$, $1\le mod\le 10^9$).
Output
Print one integer, which is the answer modulo $mod$.
4 403458273
17
Note
The following are all valid pairs $(p,q)$ when $n=4$.
- $p=[1,3,4,2]$, $q=[2,1,3,4]$,
- $p=[1,4,2,3]$, $q=[2,1,3,4]$,
- $p=[1,4,3,2]$, $q=[2,1,3,4]$,
- $p=[1,4,3,2]$, $q=[2,1,4,3]$,
- $p=[1,4,3,2]$, $q=[2,3,1,4]$,
- $p=[1,4,3,2]$, $q=[3,1,2,4]$,
- $p=[2,3,4,1]$, $q=[3,1,2,4]$,
- $p=[2,4,1,3]$, $q=[3,1,2,4]$,
- $p=[2,4,3,1]$, $q=[3,1,2,4]$,
- $p=[2,4,3,1]$, $q=[3,1,4,2]$,
- $p=[2,4,3,1]$, $q=[3,2,1,4]$,
- $p=[2,4,3,1]$, $q=[4,1,2,3]$,
- $p=[3,2,4,1]$, $q=[4,1,2,3]$,
- $p=[3,4,1,2]$, $q=[4,1,2,3]$,
- $p=[3,4,2,1]$, $q=[4,1,2,3]$,
- $p=[3,4,2,1]$, $q=[4,1,3,2]$,
- $p=[3,4,2,1]$, $q=[4,2,1,3]$.