Паша та перестановки#12294

Паша та перестановки (Розбір)

Автор задачі:	Тунчай Пашаєв
Підготовлено:	Хасан Салех (MathModel)
Редагував:	Хасан Салех (MathModel)

Розв'язок

У нас є масив $a$ розміру $n$ , масив $p$ розміру $m$ та ціле число $k$ . Перестановка $b$ масиву $a$ називається красивою, якщо для кожного $1 \leq i < m$ 1 \le i < m ми маємо $b_{p_{i}} + b_{p_{i + 1}} \equiv 0 (mod k)$ b_{p_i} + b_{p_{i+1}} \equiv 0 \pmod{k}. У реалізації нижче ми використовуємо лише той факт, що $m$ позицій формують ланцюг довжини $m$ ; нам потрібен лише $m$ , а не фактичні індекси $p$ .

Ми попередньо обчислюємо факторіали та обернені факторіали за модулем $1 0^{9} + 7$ 10^9+7 до $N = 2 \cdot 1 0^{5}$ N = 2\cdot 10^5, і визначаємо

P (n, r) = n P r = \frac{n !}{( n - r )!} (mod MOD)

P(n,r) = n P r = \frac{n!}{(n-r)!} \pmod{\text{MOD}}

як кількість способів вибрати та впорядкувати $r$ елементів з $n$ різних.

Для кожного тесту ми читаємо $a$ та будуємо:

$cnt [x]$ : кратність точного значення $x$ в $a$ (для обробки дублікатів),
$rem [r]$ : кількість елементів з залишком $r = x mod k$ r = x \bmod k.

Потім ми читаємо $p$ та ігноруємо його вміст, ми лише зберігаємо $m$ .

Якщо $m = 1$ m = 1, то жодних обмежень немає, тому кожна перестановка мультимножини $a$ є красивою. Кількість різних перестановок дорівнює

\frac{n !}{\prod _{x} ( cnt [ x ]!)} (mod MOD),

\frac{n!}{\prod_x (\text{cnt}[x]!)} \pmod{\text{MOD}},

реалізовано як $f a c t [n] \cdot \prod_{x} in v f a c t [cnt [x]]$ fact[n] \cdot \prod_x invfact[\text{cnt}[x]].

Тепер припустимо, що $m \geq 2$ m \ge 2. Лише $m$ "спеціальні" позиції обмежені. Якщо якась позиція в ланцюзі має залишок $r$ за модулем $k$ , сусід по ланцюгу повинен мати залишок

r_{2} = (k - r) mod k,

r_2 = (k - r) \bmod k,

інакше сума не дорівнює $0$ за модулем $k$ . Таким чином, залишки в ланцюзі формуються з комплементарних пар $(r, r_{2})$ (r, r_2).

Нехай

o = ⌊ \frac{m + 1}{2} ⌋, e = ⌊ \frac{m}{2} ⌋ .

o = \left\lfloor \frac{m+1}{2} \right\rfloor, \qquad e = \left\lfloor \frac{m}{2} \right\rfloor.

Якщо $r \neq = r_{2}$ r \neq r_2, то в ланцюзі залишки повинні чергуватися між $r$ та $r_{2}$ r_2. Є два шаблони: почати з $r$ (тоді нам потрібно $o$ позицій з залишком $r$ та $e$ з $r_{2}$ r_2) або почати з $r_{2}$ r_2 (тоді $o$ з $r_{2}$ r_2 та $e$ з $r$ ). Якщо $rem [r] = c_{0}$ \text{rem}[r] = c_0 та $rem [r_{2}] = c_{1}$ \text{rem}[r_2] = c_1, і обидва існують, способи призначити різні елементи на $m$ обмежених позицій дорівнюють

P (c_{0}, o) \cdot P (c_{1}, e) + P (c_{1}, o) \cdot P (c_{0}, e) .

P(c_0,o)\cdot P(c_1,e) \;+\; P(c_1,o)\cdot P(c_0,e).

Якщо $r = r_{2}$ r = r_2 (самокомплементарний залишок, наприклад, $r = 0$ r=0 або $r = k /2$ r=k/2, коли $k$ парне), тоді всі $m$ обмежених позицій повинні використовувати лише залишок $r$ , і якщо є $c_{0} = rem [r]$ c_0 = \text{rem}[r] таких елементів, кількість способів дорівнює $P (c_{0}, m)$ P(c_0,m).

Ми перебираємо всі залишки $r$ в $rem$ , обчислюємо $r_{2} = (k - r) mod k$ r_2 = (k-r)\bmod k і:

якщо $r = r_{2}$ r = r_2, ми використовуємо $c u r = P (c_{0}, m)$ cur = P(c_0,m);
якщо $r < r_{2}$ r < r_2 і $r_{2}$ r_2 існує, ми використовуємо $c u r = P (c_{0}, o) P (c_{1}, e) + P (c_{1}, o) P (c_{0}, e)$ cur = P(c_0,o)P(c_1,e) + P(c_1,o)P(c_0,e);
якщо $r > r_{2}$ r > r_2, ми пропускаємо (невпорядкована пара ${r, r_{2}}$ \{r,r_2\} обробляється, коли ми знаходимося на меншому).

Для кожної такої пари ми маємо $c u r$ способів заповнити $m$ обмежених позицій. Залишені $n - m$ n-m позицій вільні і можуть бути заповнені залишковими елементами в будь-якому порядку, додаючи фактор $(n - m)!$ (n-m)!. Таким чином, ми накопичуємо

an s + = c u r \cdot (n - m)! .

ans \mathrel{+}= cur \cdot (n-m)!.

До цього моменту кожне входження одного й того ж значення розглядається як різний маркований об'єкт. Щоб підрахувати різні перестановки мультимножини $a$ , ми ділимо на $cnt [x]!$ для кожного різного значення $x$ , тобто множимо на $in v f a c t [cnt [x]]$ invfact[\text{cnt}[x]]. Це те саме виправлення, що й у випадку $m = 1$ m=1.

Складність загалом становить $O (\sum n)$ \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()

Python