Pasha and permutations (Editorial)

Solution

We have an array $a$ of size $n$, an array $p$ of size $m$ and an integer $k$. A rearrangement $b$ of $a$ is called beautiful if for every 1 \le i < m we have b_{p_i} + b_{p_{i+1}} \equiv 0 \pmod{k}. In the implementation below we use only the fact that the $m$ positions form a chain of length $m$; we only need $m$, not the actual indices of $p$.

We precompute factorials and inverse factorials modulo 10^9+7 up to N = 2\cdot 10^5, and define

as the number of ways to choose and order $r$ elements from $n$ distinct ones.

For each test we read $a$ and build:

• $\text{cnt}[x]$: multiplicity of the exact value $x$ in $a$ (to handle duplicates),

• $\text{rem}[r]$: number of elements with remainder r = x \bmod k.

Then we read $p$ and ignore its content, we only keep $m$.

If m = 1, there are no constraints at all, so every rearrangement of the multiset $a$ is beautiful. The number of distinct permutations is

implemented as fact[n] \cdot \prod_x invfact[\text{cnt}[x]].

Now assume m \ge 2. Only the $m$ "special" positions are constrained. If some position on the chain has remainder $r$ modulo $k$, the neighbor on the chain must have remainder

otherwise the sum is not $0$ mod $k$. So remainders on the chain are built from complementary pairs (r, r_2).

Let

If r \neq r_2, then on the path the remainders must alternate between $r$ and r_2. There are two patterns: start with $r$ (then we need $o$ positions of remainder $r$ and $e$ of r_2) or start with r_2 (then $o$ of r_2 and $e$ of $r$). If \text{rem}[r] = c_0 and \text{rem}[r_2] = c_1, and both exist, the ways to assign distinct elements to the $m$ constrained positions are

If r = r_2 (self-complementary remainder, e.g. r=0 or r=k/2 when $k$ is even), then all $m$ constrained positions must use remainder $r$ only, and if there are c_0 = \text{rem}[r] such elements, the number of ways is P(c_0,m).

We iterate over all remainders $r$ in $\text{rem}$, compute r_2 = (k-r)\bmod k and:

• if r = r_2, we use cur = P(c_0,m);

• if r < r_2 and r_2 exists, we use cur = P(c_0,o)P(c_1,e) + P(c_1,o)P(c_0,e);

• if r > r_2, we skip (the unordered pair \{r,r_2\} is handled when we are at the smaller one).

For each such pair we have $cur$ ways to fill the $m$ constrained positions. The remaining n-m positions are free and can be filled with the remaining elements in any order, adding a factor of (n-m)!. So we accumulate

Up to this point, every occurrence of the same value is treated as a different labeled object. To count distinct permutations of the multiset $a$, we divide by $\text{cnt}[x]!$ for each distinct value $x$, i.e. multiply by invfact[\text{cnt}[x]]. This is the same correction as in the m=1 case.

Complexity overall is \mathcal{O}(\sum n).

MOD=1000000007
MAX=200005

fact=[1]*MAX
invfact=[1]*MAX

for i in range(1,MAX):
    fact[i]=fact[i-1]*i%MOD
    invfact[i]=pow(fact[i],MOD-2,MOD)

def P(n,r):
    if r<0 or r>n:return 0
    return fact[n]*invfact[n-r]%MOD

def solve():
    n,m,k=map(int,input().split())
    rem={}
    cnt={}
    a=list(map(int,input().split()))
    for x in a:
        r=x%k
        rem[r]=rem.get(r,0)+1
        cnt[x]=cnt.get(x,0)+1
    input().split()
    if m==1:
        ans=fact[n]
        for c in cnt.values():
            ans=ans*invfact[c]%MOD
        print(ans)
        return
    o=(m+1)//2
    e=m//2
    ans=0
    for r,c0 in rem.items():
        r2=(k-r)%k
        if r==r2:
            cur=P(c0,m)
        elif r<r2:
            if r2 in rem:
                c1=rem[r2]
                cur=(P(c0,o)*P(c1,e)+P(c1,o)*P(c0,e))%MOD
            else:
                cur=0
        else:
            continue
        ans=(ans+cur*fact[n-m])%MOD
    for c in cnt.values():
        ans=ans*invfact[c]%MOD
    print(ans)


for _ in range(int(input())):
    solve()