.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » ubergraf

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
ubergraf


Timp maxim de execuţie / test:
1.6s
Memorie totala disponibilă / stivă:
32MB / 2MB

Î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 număr 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.

Cerinţă

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

Fişierul de ieşire ubergraf.out va conţine o singură linie pe care va fi scris un număr întreg reprezentând numărul cerut.

Restricţii

1 <= N <= 300
N < P <= 30 000, P
prim
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.

Exemple

ubergraf.inubergraf.outExplicaţii
4 37 9 Cele 9 ubergraf-uri corespunzătoare primului exemplu sunt:


60 9221 2385

autor: Paul Băltescu
propunător: Prof. Emanuela Cerchez
Liceul de Informatică ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la Lot VN 2010: rege, cd1, albine1, cifru3, puteri35, regat, parpal, ppcover, kcons, kdtree, pokemon, permutare, fibo1
De acelaşi autor: matrice, radio1
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, plimbare, party, pc, pioni, seif, iepuri, numere3, perm, ture, bilete, prop, ro, reduceri, cuburi, invest, cutie2, stalpi, nr2, judete, strict, auto2, tree, jobs, leaves, pstring, program, datorii, senzori, farfurii, joc1, barbie, ambigram, rlcs, cub1, bio, chimie1, otilia, pasune, remi, sir23, tren1, joc5, pachete, echipe, comb, agitatie, ivv, peste, pitici, pipe, shgraf, tabara1, stop, randuri, zidar, log, sant, produs, subsir, cover, bcast, emax, dist, mesaj1, imax, avere, asmax, raft, suma2, joc12, fni, nr4, join, transport, masina3, lsort, microvirus, fat, cafea, echipe1, anticip, bsir, diamant, petrom, evantai, spion, acolor, evo, bombo, lacusta, lant, team, pitici1, numere8, dep, stiva, subgeom, pviz, tir1, cabane, piramida1, mosia, cuvinte1, gaina, materom, sortari, turnuri, trans, politie, codul, dansatori, nkbiti, kperms, treegame, siruri2, 123, jucarii, bradut, joc15, expozitie, text3, ic, echilibru, distsir, kmax, stalpi1, gaz, triunghi2, v2d, cuiburi, mine, orientare, activ, secvbiti, kcons, pokemon, left, acerc, autostrazi, kdist, select, cazare, fluviu, telecomanda, parcela, pion, subs, suma4, sirmax, bdotcom, viena, sablon2, telecab, ikebana, radare, hacker, obstacole, robotel, centrala, verigi, cds, wg, minusk, radioactiv, enigma, jb, efect, maxviz, ripstick, progresii, maxtri, combcuv, blis, subsiruri, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
Despre graf: gropi, tgv, matrice2, miniasm, picnic, mere, circuit, soldati, arce, conflicte, desen, robot, furtuna, net, cuvinte, excursie, cadere, pioni, reinvent, kreg, flood, croco, johnie, matrice, arthur, kimberley, ro, sol, caravane, bete, honest, police, pcod, zmeu, auto2, grazing, datorii, trafic, sponsori, monede1, apm, bile1, caini, masina1, bomboane, turn1, shgraf, paintball, program1, tgraf, kgb, algola, felinar, joc6, tric, homeless, promo, turism, casute, joc10, prieteni1, traseu, zapezi, litoral, lover, trip, garaj, ziduri, tv, pact, echipe1, vitale, spion, trasee, bcolor, scara2, lant, ab3, soc, team, gard, rsp, graf, mexc, dep, albinuta1, atac2, cabane, drumuri, tj, grade, jungla, lanterna, magic5, coment, urgenta, fazan, lanturi, cfr, site, traseu1, trmv, graphgame, minuni, telefon, carray, pestera, chei, arbgraf, war, fluviu, drumuri1, entries, ubuntzei, pack, fotbal1, pamant, dag, razboi, benzina2, wg, neconex, asfalt1, kubus2, module, progresii, dfs, prieteni3, megascoala, grafxy, dineu, vot1, biperm, drumuri2, nrgraf, cristal, cartite, copaci3, dragoni, nuclee
surse trimise | ajutor