Fişierul intrare/ieşire:wwt.in, wwt.outSursăAlgoritmiada 2018 Runda Finala
AutorAdrian BudauAdăugată de
Timp execuţie pe test1 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Wwt

Este anul 21XX, si te aflii pe planeta misterioasa Algo. Ai fost trimis de imperiul malefic Adaimtir sa provocati un al treilea razboi mondial pe acceasta planeta.
Pe planeta Algo exista un singur continent, pe care il putem vizualiza ca pe o insiruire de N parcele de pamant. Exista de asemenea K tari, cu indici de la 1 la K. Fiecare parcela de pamant este detinuta de cate o tara. Spunem ca doua tari A si B sunt in conflict daca si numai daca tara A detine o parcela x si tara B detine o parcela y astfel incat x si y sunt adiacente.
Cu ajutorul fondurilor date tie de catre imperiu, tu ai de gand sa creezi o noua tara, care poate cumpara oricate parcele de la oricare alte tari, cu scopul de a aduce lumea in pragul unui razboi mondial. Acest lucru se intampla daca si numai daca tarile pot fi partitionate in doua multimi P si Q astfel incat:

  • nicio pereche de tari din P nu se afla in conflict
  • nicio pereche de tari din Q nu se afla in conflict
  • exista cel putin o tara A din P si cel putin o tara B din Q astfel incat A si B sunt in conflict.

Acum te intrebi: "oare in cate moduri pot cumpara parcele astfel incat sa aduc lumea in pragul unui razboi mondial ?" Doua moduri de a cumpara parcele se considera diferite daca si numai daca exista o parcela cumparata in una care nu este cumparata in cealalta.

Date de intrare

Fişierul de intrare wwt.in va contine, pe primul rand, numerele N si K.
Pe al doilea rand vor aparea N numere, unde al i-lea numar reprezinta indicele tarii ce detine ce-a de a i-a parcela.

Date de ieşire

În fişierul de ieşire wwt.out va contine numarul cerut, modulo 1 000 000 007.

Restricţii

  • 1 ≤ N ≤ 200
  • 1 ≤ K ≤ 10
  • Pentru teste in valoare de 9 puncte, N ≤ 15 si K ≤ 3
  • Pentru alte teste in valoare de inca 33 de puncte, K ≤ 5
  • Pentru alte teste in valoare de inca 25 de puncte, K ≤ 8
  • Parcelele detinute de o tara nu trebuie neaparat sa fie continue
  • Este posibil ca o tara sa nu detina nicio parcela.

Exemplu

wwt.inwwt.out
4 3
1 2 3 1
11
10 3
1 2 3 2 2 2 3 1 3 3
423

Explicaţie

In primul exemplu, daca indicele tarii noi este 4, atunci urmatoarele sunt moduri valide de a cumpara parcele:

  • 4 2 3 1
  • 1 2 3 4
  • 1 4 3 4
  • 4 4 3 1
  • 4 4 3 4
  • 4 2 4 1
  • 1 2 4 4
  • 4 2 4 4
  • 4 4 4 1
  • 1 4 4 4
  • 1 4 4 1
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?