Editing 2048 - mixperm

Se consideră două șiruri de numere naturale, ambele de lungime <code>n</code>, <code>a=(a[1],a[2],...,a[n])</code> și <code>b=(b[1],b[2],...,b[n])</code>. Se știe că elementele din cele două șiruri sunt numere naturale, nu neapărat distincte, din mulțimea <code>{1,2,…,n}</code>. Cu cele două șiruri se poate face următoarea operație: se aleg doi indici <code>i</code> și <code>j</code>, cu <code>1≤i≤j≤n</code>, apoi prin interschimbarea secvențelor <code>a[i],a[i+1],...,a[j]</code> cu <code>b[i],b[i+1],...,b[j]</code> se obțin șirurile:

* <code>a[1], a[2], ...,a[i-1], b[i],b[i+1],…, b[j], a[j+1],a[j+2], …, a[n]</code>  și
* <code>b[1], b[2], ...,b[i-1], a[i], a[i+1],…, a[j], b[j+1],b[j+2], …, b[n]</code>.

Dacă măcar unul din șirurile obținute este permutare a mulțimii <code>{1,2,...,n}</code>, atunci spunem că s-a obținut un ''mixperm''.

= Cerința =
Să se determine în câte moduri se poate obține un ''mixperm''.

= Date de intrare =
Fișierul de intrare <code>mixperm.in</code> conţine pe prima linie numărul natural n, pe linia a doua, separate prin câte un spațiu, numerele <code>a[1]</code>, <code>a[2]</code>, …, <code>a[n]</code>, iar pe linia a treia, separate prin câte un spațiu, numerele <code>b[1]</code>, <code>b[2]</code>, …, <code>b[n]</code>.

= Date de ieșire =
Fișierul de ieșire <code>mixperm.out</code> va conţine un singur număr natural reprezentând numărul de posibilități de a se obține un mixperm.

= Restricții și precizări =

* <code>1 ≤ n ≤ 10.000</code>

= Exemplu: =
<code>mixperm.in</code>
 6
 3 2 1 4 4 5
 2 3 3 4 6 5
<code>mixperm.out</code>
 8

=== Explicație ===
Se pot interschimba secvențele care au ca poziții de început și sfârșit <code>(1,3) (1,4) (3,3) (3,4) (4,6) (5,6) (4,5) (5,5)</code>.

De exemplu, la interschimbarea secvenţei date de intervalul <code>(3,4)</code> se obţin şirurile <code>(3,2,3,4,4,5)</code> şi <code>(2,3,1,4,6,5)</code>. Al doilea şir este o permutare.


== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import sys

nmax = 10005
inFile = "mixperm.in"
outFile = "mixperm.out"

a = [0] * nmax
b = [0] * nmax
sta = [0] * nmax
dra = [0] * nmax
stb = [0] * nmax
drb = [0] * nmax
suma_st = [0] * nmax
sumb_st = [0] * nmax
suma_dr = [0] * nmax
sumb_dr = [0] * nmax
app_st = [0] * nmax
bpp_st = [0] * nmax
app_dr = [0] * nmax
bpp_dr = [0] * nmax

S = 0
sTotal = 0
sPP = 0

def Citire():
    fin = open(inFile, 'r')
    global n
    n = int(fin.readline())
    a[1:n+1] = map(int, fin.readline().split())
    b[1:n+1] = map(int, fin.readline().split())
    fin.close()

def Precalculare():
    global S, sTotal, sPP
    S = 0
    sTotal = n * (n + 1) // 2
    sPP = 1 * n * (n + 1) * (2 * n + 1) // 6
    for i in range(1, n+1):
        S = S ^ i
        sta[i] = sta[i - 1] ^ a[i]
        stb[i] = stb[i - 1] ^ b[i]
        suma_st[i] = suma_st[i - 1] + a[i]
        sumb_st[i] = sumb_st[i - 1] + b[i]
        app_st[i] = app_st[i - 1] + a[i] * a[i]
        bpp_st[i] = bpp_st[i - 1] + b[i] * b[i]
    for i in range(n, 0, -1):
        dra[i] = dra[i + 1] ^ a[i]
        drb[i] = drb[i + 1] ^ b[i]
        suma_dr[i] = suma_dr[i + 1] + a[i]
        sumb_dr[i] = sumb_dr[i + 1] + b[i]
        app_dr[i] = app_dr[i + 1] + a[i] * a[i]
        bpp_dr[i] = bpp_dr[i + 1] + b[i] * b[i]

def Valid(j, i, aSum, bSum):
    if ((S ^ sta[j - 1] ^ bSum ^ dra[i + 1]) == 0 and sTotal == suma_st[j-1] + suma_dr[i+1] + (sumb_st[i] - sumb_st[j - 1]) and sPP == app_st[j-1] + app_dr[i+1] + (bpp_st[i] - bpp_st[j - 1])):
        return True
    if ((S ^ stb[j - 1] ^ aSum ^ drb[i + 1]) == 0 and sTotal == sumb_st[j-1] + sumb_dr[i+1] + (suma_st[i] - suma_st[j - 1]) and sPP == bpp_st[j-1] + bpp_dr[i+1] + (app_st[i] - app_st[j - 1])):
        return True
    return False

def Rezolvare():
    ans = 0
    for i in range(1, n+1):
        aSum = bSum = 0
        for j in range(i, 0, -1):
            aSum = aSum ^ a[j]
            bSum = bSum ^ b[j]
            if (Valid(j, i, aSum, bSum)):
                ans += 1

    fout = open(outFile, 'w')
    fout.write(str(ans) + "\n")
    fout.close()

if __name__ == "__main__":
    Citire()
    Precalculare()
    Rezolvare()
</syntaxhighlight>