Summer FLASG Advanced | SpiridușiAdvanced

This was the problem page during the contest. Access the current page here.
Time limit: 0.05s Memory limit: 64MB Input: Output:

ASG s-a jucat prea mult Fortnite. A vrut să se bage în pat, însă Flaviu îl aștepta acolo. Acesta nu a știut să rezolve o problemă la matematică cu restul împărțirii de la școală și i-a cerut ajutorul. Între timp, a venit Spiridușul Binar care i-a dat tema lui Flaviu și, știindu-l mai informatician din fire, i-a dat o problemă mult mai grea, deoarece are încredere în ASG să-i salveze poporul.

Spiridușul Binar face parte din regatul digital Bitlandia, unde există două orașe: Bitești și Octești. Aceste orașe sunt în competiție constantă să vadă cine poate genera cel mai puternic semnal. Fiecare oraș are un dispozitiv de criptare care ia două chei aa și bb, și le combină cu o frecvență de modulare xx pentru a calcula puterea semnalului, prin operația (ax)(bx)(a \oplus x) \cdot (b \oplus x), unde \oplus reprezintă operația xor.

Cerință

Ajutați-l pe Spiriduș să găsească puterea semnalului maximă ce se poate forma cu cheile aa și bb, pentru a-i întrece pe cei din orașul Octești.

Puterea semnalului poate fi foarte mare, așadar să se afișeze puterea modulo 1 000 741 8231\ 000\ 741\ 823.

Date de intrare

Pe prima linie se găsește numărul NN, ce reprezintă lungimea maximă a cheilor.

Pe a doua linie se găsește șirul binar AA, iar pe a treia linie șirul binar BB, ambele de lungime NN.

Date de ieșire

Pe prima linie se va găsi un singur număr întreg, anume puterea semnalului maximă modulo 1 000 741 8231\ 000\ 741\ 823.

Restricții și precizări

  • 1N1 0001 \leq N \leq 1\ 000;
  • 1A,B2N1 \leq A, B \leq 2^N.
  • 0x2N0 \leq x \leq 2^N.
  • AA și BB au aceeași lungime.
# Punctaj Restricții
1 8 N20N \leq 20
2 16 N50N \leq 50
3 40 N100N \leq 100
4 36 Fără restricții suplimentare

Exemplul 1

stdin

5
10101
00110

stdout

420

Explicație

Șirul binar AA este numărul 2121, iar celălalt este numărul 66. Pentru x=2x = 2, avem (212)(62)=92(21 \oplus 2) \cdot (6 \oplus 2) = 92. Pentru x=8x = 8, avem (218)(68)=238(21 \oplus 8) \cdot (6 \oplus 8) = 238. x=9x = 9 oferă puterea maximă de 420420.

Exemplul 2

stdin

7
1110101
0010110

stdout

5796

Explicație

Șirul AA reprezintă numărul 117117 și șirul BB reprezintă numărul 2222. Puterea maximă este atinsă în x=41x = 41 și x=74x = 74.

Log in or sign up to be able to send submissions!