Fișierul intrare/ieșire dejavu.in, dejavu.out Sursă selecție lot Nerdvana 2024
Autor Cătălin Frâncu Adăugată de avatar Catalin.Francu Cătălin Frâncu • Catalin.Francu
Timp de execuție pe test 0.45 sec Limită de memorie 524288 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip halfstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Déjà vu

Un șir déjà vu de lungime N este un șir de N elemente naturale, cu valori între 1 și N, cu proprietatea că orice valoare apare de cel mult două ori în șir.

Să considerăm lista L a tuturor șirurilor déjà vu de lungime N, ordonate lexicografic. Reamintim că un șir X stă înaintea altui șir Y în această listă dacă există un indice k astfel încît Xi = Yi pentru i < k și Xk < Yk. Primul șir din listă are numărul de ordine 0.

Date fiind un număr N, un număr Q și Q șiruri déjà vu de lungime N, să se determine numerele de ordine ale acestor șiruri în lista L. Deoarece lista poate fi foarte lungă, afișați răspunsurile modulo 1.000.000.007.

Date de intrare

Fișierul de intrare dejavu.in conține pe prima linie numerele N și Q. Următoarele Q linii conțin cîte un șir déjà vu sub forma a N numere separate prin spații.

Date de ieșire

În fișierul de ieșire dejavu.out afișați numerele de ordine modulo 1.000.000.007, cîte unul pe linie.

Restricții

  • 1 ≤ N ≤ 5.000
  • 1 ≤ Q ≤ 100
subtask puncte restricții
1 15 N ≤ 8; Q = 1
2 60 Q = 1
3 25 Fără restricții suplimentare.

Testele nu sînt grupate.

Exemple

dejavu.in dejavu.out
3 2
2 2 3
1 3 1
 12
5
10 2
1 10 4 9 5 2 4 1 9 6
9 4 5 8 4 7 1 2 3 8
 370115914
309643429

Explicație

Pentru primul exemplu, șirurile déjà vu de lungime 3 sînt:

număr de ordine șir
0 112
1 113
2 121
3 122
4 123
5 131
6 132
7 133
8 211
9 212
10 213
11 221
12 223
... ...

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 5 categorii