Fişierul intrare/ieşire:ubergraf.in, ubergraf.outSursăLot Vrancea 2010, Baraj 3
AutorAlexandru Tomescu, Paul-Dan BaltescuAdăugată deMishu91Andrei Misarca Mishu91
Timp execuţie pe test0.35 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Ubergraf

În urma succesului internaţional al shgraf-urilor Mirunei, Laura s-a hotarât să lanseze propriul ei tip de graf, numit ubergraf. Un ubergraf este un graf orientat, aciclic, neetichetat, cu proprietatea că mulţimile vecinilor oricăror două vârfuri diferite sunt distincte.

Să considerăm următoarele exemple de grafuri:

Se observă că primul exemplu nu este un ubergraf, deoarece există două vârfuri a caror mulţime de vecini este mulţimea vidă (cele două vârfuri cu grad extern 0). Nici cel de-al doilea exemplu nu este un ubergraf, deoarece cele două vârfuri cu grad intern 0 au aceeaşi mulţime de vecini. Cel de-al treilea exemplu este un ubergraf. Ultimul exemplu nu este un ubergraf, pentru că nu este un graf aciclic. Laura întampină acum o nouă problemă: fiind dat un numar natural N, ar dori dori să ştie câte ubergraf-uri distincte cu N vârfuri există. Cum numărul de ubergraf-uri poate fi foarte mare, ea se mulţumeşte dacă îi spuneţi rezultatul modulo P, unde P este un număr prim dat.

Determinaţi numărul de ubergraf-uri cu N noduri modulo P.

Date de intrare

Pe prima linie a fişierului de intrare ubergraf.in se află două numere întregi N şi P cu semnificaţia din enunţ.

Date de ieşire

În fişierul de ieşire ubergraf.out se află un singur număr întreg reprezentând numărul cerut.

Restricţii

  • 1 ≤ N ≤ 300
  • N < P ≤ 30 000, P prim
  • Pentru 65% din teste N ≤ 150.
  • Două ubergraf-uri se consideră distincte dacă nu există nici o bijecţie de la mulţimea vârfurilor în mulţimea vârfurilor astfel încât între două vârfuri să existe arc dacă şi numai dacă există arc între vârfurile corespondente.

Exemplu

ubergraf.inubergraf.outubergraf.inubergraf.out
4 37
9
60 9221
2385

Explicaţie

Cele 9 ubergraf-uri corespunzătoare primului exemplu sunt:

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content