* 'NrChei':algoritmiada-2022/runda-4/solutii#nrchei
==include(page="solutie/nrchei")==

 
h2(#xorseq). Solutia problemei 'XorSeq':problema/xorseq
 
Observăm, în primul rând, că soluţia problemei poate fi exprimată, în mod echivalent, ca suma din 2 la puterea lungimii fiecărei secvenţe a cărui $xor$ este 0. Echivalent, dacă $v[i]$ este $xor$-ul prefixului de lungime $i$ a secvenţei, vrem sumă din $2^j-i^$ pentru $i < j$ şi $v[i] = v[j]$. În mod echivalent, $2^j-i^ = 2^j^/2^i^$; aşadar, pentru a rezolva problema, vom parcurge şirul cu $j$ de la 0 la $n$, menţinând un şir auxiliar $a[x]$, unde $a[x]$ este suma din $1/2^i^$ pentru $i < j$ şi $v[i] = x$. Şirul trebuie modificat în doar o poziţie la fiecare incrementare a lui $j$; mai mult, contribuţia poziţiei $j$ la rezultat va fi $2^j^ * a[v[j]]$.
 
h2(#zelda). Solutia problemei 'Zelda':problema/zelda

private

protected