Fişierul intrare/ieşire:xorseq.in, xorseq.outSursăAlgoritmiada 2022, Runda 4
AutorTamio-Vesa NakajimaAdăugată deRuxandra985Nanu Ruxandra Laura Ruxandra985
Timp execuţie pe test0.2 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Xorseq

Azusa, vrăjitoarea din munţi, a primit de curând un învăţăcel, dragonul Laika, care speră să înveţe secretele puterii incredibile a Azusei. Din nefericire pentru Laika, sursa puterii Azusei nu e nimic special: doar a exersat puţin câte puţin pentru mult timp. Dar cum tot o roagă pe Azusa să îi dea ceva de făcut, Azusa a inventat urmăţoarea problemă de informatică.

Azusa îi dă Laikăi un şir de N numere naturale, şi apoi o întreabă câte perechi de subşiruri satisfac simultan următoarele trei condiţii:

  1. Subşirurile sunt disjuncte.
  2. Reunite, subşirurile formează o subsecvenţă.
  3. Subşirurile au xor-ul pe biţi egal.

Date de intrare

Fişierul de intrare xorseq.in conţine pe primul rând pe N, şi pe al doilea rând şirul dat.

Date de ieşire

În fişierul de ieşire xorseq.out se va afişa numărul cerut, modulo 10^9+7.

Restricţii

  • 1 ≤ N ≤ 200.000
  • 0 ≤ un element al şirului < 220.
  • Pentru 10 de puncte, 1 ≤ N ≤ 15.
  • Pentru alte 30 de puncte, 1 ≤ N ≤ 2.000.
  • Pentru alte 20 de puncte, şirul este ales aleator din mulţimea de şiruri posibile de lungimea sa.

Exemplu

xorseq.inxorseq.out
4
0 1 1 0
20
20
3 2 3 1 3 1 2 3 1 1 2 0 1 2 3 2 1 1 3 0
643678

Explicaţie

În primul exemplu, perechile de subşiruri ce satisfact condiţiile cerute sunt enumerate mai jos. Fiecare pereche este scrisă ca o pereche de mulţimi de indici; astfel perechea (1, 3), (2, 4) reprezintă o pereche de subşiruri unde primul subşir conţine primul şi al treilea element, şi al doilea subşir conţine al doilea şi al patrulea element.

  1. (), (1)
  2. (), (1, 2, 3)
  3. (1 ), (2, 3)
  4. (2 ), (1, 3)
  5. (1, 2), (3)
  6. (), (1, 2, 3, 4)
  7. (1 ), (2, 3, 4)
  8. (2 ), (1, 3, 4)
  9. (1, 2), (3, 4)
  10. (3 ), (1, 2, 4)
  11. (1, 3), (2, 4)
  12. (2, 3), (1, 4)
  13. (1, 2, 3), (4)
  14. (), (2, 3)
  15. (2 ), (3)
  16. (), (2, 3, 4)
  17. (2 ), (3, 4)
  18. (3 ), (2, 4)
  19. (2, 3), (4)
  20. (), (4)
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?