CF1542E2 Abnormal Permutation Pairs (hard version)

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.

N/A

N/A

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] $ .