Paşa və permutasiya#12294

Paşa və permutasiya (Həll təhlili)

Problem Müəllifi:	Tuncay Pashayev
Hazırlayan:	Hasan Saleh (MathModel)
Redaktə edən:	Hasan Saleh (MathModel)

Həll

Bizim $n$ ölçülü $a$ massivimiz, $m$ ölçülü $p$ massivimiz və bir tam ədəd $k$ var. $a$ massivinin bir permutasiya $b$ gözəl adlanır, əgər hər $1 \leq i < m$ 1 \le i < m üçün $b_{p_{i}} + b_{p_{i + 1}} \equiv 0 (mod k)$ b_{p_i} + b_{p_{i+1}} \equiv 0 \pmod{k} olarsa. Aşağıdakı implementasiyada yalnız $m$ mövqelərinin $m$ uzunluğunda bir zəncir formalaşdırdığını bilirik; bizə yalnız $m$ lazımdır, $p$ -nin faktiki indeksləri lazım deyil.

Biz $N = 2 \cdot 1 0^{5}$ N = 2\cdot 10^5-ə qədər $1 0^{9} + 7$ 10^9+7 modulunda faktorialları və tərs faktorialları əvvəlcədən hesablayırıq və

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}}

şəklində müəyyən edirik, bu da $n$ fərqli elementdən $r$ element seçmək və sıralamaq üçün yolların sayıdır.

Hər test üçün $a$ -yı oxuyuruq və aşağıdakılara əsaslanaraq qururuq:

$cnt [x]$ : $a$ -da dəqiq dəyər $x$ -in çoxluğu (təkrarlananları idarə etmək üçün),
$rem [r]$ : $r = x mod k$ r = x \bmod k olan elementlərin sayı.

Sonra $p$ -ni oxuyuruq və onun məzmununu nəzərə almırıq, yalnız $m$ -ni saxlayırıq.

Əgər $m = 1$ m = 1-dirsə, heç bir məhdudiyyət yoxdur, buna görə də $a$ multisetinin hər bir permutasiya gözəldir. Fərqli permutasiya sayısı

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

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

şəklindədir, bu da $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]] kimi həyata keçirilir.

İndi $m \geq 2$ m \ge 2 olduğunu düşünək. Yalnız $m$ "xüsusi" mövqelər məhdudlaşdırılmışdır. Əgər zəncirdəki bir mövqenin $k$ modulunda qalıq $r$ -dirsə, zəncirdəki qonşu $r$ -in qalıq $r_{2} = (k - r) mod k$ r_2 = (k - r) \bmod k olmalıdır, əks halda cəmi $0$ mod $k$ olmayacaq. Beləliklə, zəncirdəki qalıqlar tamamlayıcı cütlər $(r, r_{2})$ (r, r_2) şəklində qurulur.

Tutaq ki,

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.

Əgər $r \neq = r_{2}$ r \neq r_2-dirsə, o zaman zəncirdəki qalıqlar $r$ və $r_{2}$ r_2 arasında dəyişməlidir. İki naxış var: $r$ ilə başlamaq (onda $r$ qalıqlı $o$ mövqeyi və $r_{2}$ r_2 qalıqlı $e$ mövqeyi lazımdır) və ya $r_{2}$ r_2 ilə başlamaq (onda $r_{2}$ r_2 qalıqlı $o$ və $r$ qalıqlı $e$ mövqeyi lazımdır). Əgər $rem [r] = c_{0}$ \text{rem}[r] = c_0 və $rem [r_{2}] = c_{1}$ \text{rem}[r_2] = c_1 varsa və hər ikisi də varsa, $m$ məhdudlaşdırılmış mövqelərə fərqli elementləri təyin etmə yolları

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).

Əgər $r = r_{2}$ r = r_2 (öz-özünə tamamlayıcı qalıq, məsələn, $r = 0$ r=0 və ya $r = k /2$ r=k/2 $k$ cüt olduqda), onda bütün $m$ məhdudlaşdırılmış mövqelər yalnız $r$ qalıqdan istifadə etməlidir və əgər $c_{0} = rem [r]$ c_0 = \text{rem}[r] belə elementlər varsa, yolların sayı $P (c_{0}, m)$ P(c_0,m)-dir.

Biz $rem$ -dəki bütün qalıqlar $r$ -ni dövr edirik, $r_{2} = (k - r) mod k$ r_2 = (k-r)\bmod k hesablayırıq və:

əgər $r = r_{2}$ r = r_2-dirsə, $c u r = P (c_{0}, m)$ cur = P(c_0,m) istifadə edirik;
əgər $r < r_{2}$ r < r_2-dirsə və $r_{2}$ r_2 varsa, $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) istifadə edirik;
əgər $r > r_{2}$ r > r_2-dirsə, keçirik (sırasız cüt ${r, r_{2}}$ \{r,r_2\} daha kiçik olan zaman idarə olunur).

Belə cütlər üçün $c u r$ yolları $m$ məhdudlaşdırılmış mövqələri doldurmaq üçün var. Qalan $n - m$ n-m mövqeləri sərbəstdir və qalan elementlərlə istənilən sırada doldurula bilər, bu da $(n - m)!$ (n-m)! faktoru əlavə edir. Beləliklə, biz

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

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

Bu nöqtəyə qədər, eyni dəyərin hər bir görünüşü fərqli etiketli obyekt kimi qəbul edilir. $a$ multisetinin fərqli permutasiyalarını saymaq üçün, biz hər bir fərqli dəyər $x$ üçün $cnt [x]!$ ilə bölürük, yəni $in v f a c t [cnt [x]]$ invfact[\text{cnt}[x]] ilə vururuq. Bu, $m = 1$ m=1 halındakı eyni düzəlişdir.

Ümumi mürəkkəblik $O (\sum n)$ \mathcal{O}(\sum n)-dir.

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