Fişierul intrare/ieşire:matsum.in, matsum.outSursăInfoPro, Runda 4, Grupa A
AutorCostin Oncescu, Tamio-Vesa NakajimaAdăugată detamionvTamio Vesa Nakajima •tamionv
Timp execuţie pe test0.75 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Matsum

Se dau două numere întregi N, M şi două şiruri de numere întregi nenegative P, de N elemente, şi Q, de M elemente. Se defineşte apoi matricea A cu N linii şi M coloane, unde elementul Ai, j de pe linia i şi coloana j este definit de relaţia

A_{i, j} = (P_i \times Q_j) \texttt{ xor } P_i \texttt{ xor } Q_j

Operatorul xor reprezintă sau-ul exclusiv pe biţi, scris ^ în C++.

Definim valoarea S(a,b,c,d), pentru 1 ≤ a ≤ b ≤ N, 1 ≤ c ≤ d ≤ M, astfel:

S(a,b,c,d) = \sum_{i = a}^b \sum_{j = c}^d A_{i, j}

Akane este o fire mai curioasă, şi vrea să afle următoarea valoare:

\sum_{1 \leq a \leq b \leq N} \sum_{1 \leq c \leq d \leq M} S(a, b, c, d)^2

O puteţi ajuta să calculeze această valoare, modulo 109 + 7?

Date de intrare

Fişierul de intrare matsum.in conţine, pe primul rând, numerele N, M, cu semnificaţia din enunţ. Pe al doilea rând se găsesc N numere, elementele şirului P. Pe al treilea rând se găsesc M numere, elementele şirului Q.

Date de ieşire

În fişierul de ieşire matsum.out se va afişa pe primul rând un număr întreg reprezentând valoarea cerută, modulo 10^9 + 7.

Restricţii

  • 1 ≤ N, M ≤ 2.000.
  • 0 ≤ Pi, Qj ≤ 104, pentru 1 ≤ i ≤ N, 1 ≤ j ≤ M.
  • Pentru 30 de puncte, 1 ≤ N, M ≤ 30.
  • Pentru alte 40 de puncte, 1 ≤ N, M ≤ 300.
matsum.inmatsum.out
3 1
1 1 1
0
20
3 1
1 2 3
0		84
3 2
1 2 3
1 2		912
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?