Fişierul intrare/ieşire: | xorseq.in, xorseq.out | Sursă | Algoritmiada 2022, Runda 4 |
Autor | Tamio-Vesa Nakajima | Adăugată de | Nanu Ruxandra Laura •Ruxandra985 |
Timp execuţie pe test | 0.2 sec | Limită de memorie | 256000 kbytes |
Scorul tău | N/A | Dificultate | N/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:
- Subşirurile sunt disjuncte.
- Reunite, subşirurile formează o subsecvenţă.
- 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.in | xorseq.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, 3)
- (1 ), (2, 3)
- (2 ), (1, 3)
- (1, 2), (3)
- (), (1, 2, 3, 4)
- (1 ), (2, 3, 4)
- (2 ), (1, 3, 4)
- (1, 2), (3, 4)
- (3 ), (1, 2, 4)
- (1, 3), (2, 4)
- (2, 3), (1, 4)
- (1, 2, 3), (4)
- (), (2, 3)
- (2 ), (3)
- (), (2, 3, 4)
- (2 ), (3, 4)
- (3 ), (2, 4)
- (2, 3), (4)
- (), (4)