Fişierul intrare/ieşire:cuvinte6.in, cuvinte6.outSursăONSEPI, clasele 11-12
AutorAlexandra UdristoiuAdăugată deNicolaalexandraNicola Alexandra Mihaela Nicolaalexandra
Timp execuţie pe test0.25 secLimită de memorie512000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Cuvinte6

Se dau N cuvinte formate doar din primele K litere mici ale alfabetului englez şi un şir xi de M numere naturale. Trebuie să se formeze M cuvinte astfel încât oricare cuvânt i ( 1 ≤ i ≤ M ) să respecte următoarele proprietăţi:

  • Să aibă lungimea xi
  • Să fie format doar din primele K litere mici ale alfabetului englez
  • Să nu existe niciun cuvânt cuv din cele N date iniţial sau din celelalte M − 1 nou formate astfel încât cuv să fie prefix al cuvântului i
  • Să nu existe niciun cuvânt cuv din cele N date iniţial sau din celelalte M − 1 nou formate astfel încât cuvântul i să fie prefix al lui cuv

Să se calculeze numărul de moduri de a forma M cuvinte care respectă proprietăţile de mai sus. Două moduri se consideră diferite dacă există cel puţin o poziţie i pentru care al i-lea cuvânt diferă. Deoarece acest număr poate fi foarte mare, se va afişa doar restul său la împărţirea cu 1.000.000.007.

Date de intrare

Fişierul de intrare cuvinte6.in conţine pe prima linie 3 numere naturale separate prin câte un spaţiu N, M şi K, având semnificaţia din enunţ. Pe următoarele N linii se află câte un şir de caractere reprezentând cuvintele iniţiale. Ultimele M linii conţin câte un număr natural xi, reprezentând lungimile cuvintelor care trebuie construite.

Date de ieşire

În fişierul de ieşire cuvinte6.out se va afişa pe o singură linie cu numărul de moduri de a forma cele M cuvinte modulo 1.000.000.007.

Restricţii

  • 1 ≤ N ≤ 300000
  • 1 ≤ M ≤ 300000
  • 1 ≤ xi ≤ 300000, pentru orice 1 ≤ i ≤ M
  • Fie S suma lungimilor celor N cuvinte iniţiale. Atunci 1 ≤ S ≤ 300000
  • 1 ≤ K ≤ 26
  • Se garantează că toate cuvintele iniţiale vor fi formate doar din primele K litere mici ale alfabetului englez.

Subtaskuri

  • Subtask 1 (8 puncte)
    • K = 2
    • \sum_{i = 1}^{M} x_i \leq 18
    • S ≤ 20
  • Subtask 2 (19 puncte)
    • 1 ≤ N,M,S,xi ≤ 1000
  • Subtask 3 (11 puncte)
    • 1 ≤ N,S ≤ 1000
    • 1 ≤ M,xi ≤ 300000
  • Subtask 4 (12 puncte)
    • xi > lungimea oricărui cuvânt iniţial dintre cele N, pentru orice 1 ≤ i ≤ N
  • Subtask 5 (11 puncte)
    • M = 1
  • Subtask 6 (7 puncte)
    • N = 1
  • Subtask 7 (32 de puncte)
    • Fără restricţii suplimentare

Exemplu

cuvinte6.incuvinte6.out
4 2 2
ab
abaa
bbb
baaa
3
3
12
6 5 3
aab
aabcc
aabb
bbb
bb
aaaab
2
3
6
5
5
925829353

Explicaţie

În primul exemplu, există 4 posibilităţi de a forma un cuvânt de lungime 3: aaa, aab, bab, bba, şi 12 posibilităţi de a forma două cuvinte de lungime 3.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?