Diferente pentru problema/karb2 intre reviziile #8 si #2

Diferente intre titluri:

Karb2
karb2

Diferente intre continut:

== include(page="template/taskheader" task_id="karb2") ==
În perioada Campionatului Mondial din Brazilia se preconizează o creştere a traficului de cafea. Se ştie că sunt $N$ orase, conectate prin $N-1$ străzi bidirecţionale, astfel încat se poate ajunge din orice oraş în altul. În prezent există $K$ carteluri de cafea aflate în oraşe distincte, care îşi exercita influenţa în propriul oraş. Se ştie că fiecare din aceste carteluri doreşte să-şi extindă influenţa în oraşele vecine. Astfel, la un moment de timp, un cartel poate să-şi extindă influenţa într-un oraş vecin doar dacă acesta nu se află sub influenţa altui cartel. O dată ce un cartel îşi extinde influenta asupra unui nou oraş, cartelul îşi poate extinde influenţa şi în oraşele vecine acestuia. Se ştie că până la începerea campionatului mondial, fiecare oraş va fi sub influenţa unui cartel. ABIN (Agência Brasileira de Inteligência) doreşte să afle în câte moduri poate fi dominată ţara de influenţele celor $K$ carteluri la data începerii campionatului mondial, modulo $666013$.
În perioada Campionatului Mondial din Brazilia se preconizează o creştere a traficului de cafea. Se ştie că sunt N orase, conectate prin N-1 străzi bidirecţionale, astfel încat se poate ajunge din orice oraş în altul. În prezent există K carteluri de cafea aflate în oraşe distincte, care îşi exercita influenţa în propriul oraş. Se ştie că fiecare din aceste carteluri doreşte să-şi extindă influenţa în oraşele vecine. Astfel, la un moment de timp, un cartel poate să-şi extindă influenţa întrun oraş vecin doar dacă acesta nu se află sub influenţa altui cartel. O dată ce un cartel îşi extinde influenta asupra unui nou oraş, cartelul îşi poate extinde influenţa şi în oraşele vecine acestuia. Se ştie că până la începerea campionatului mondial, fiecare oraş va fi sub influenţa unui cartel. ABIN (Agência Brasileira de Inteligência) doreşte să afle în câte moduri poate fi dominată ţara de influenţele celor K carteluri la data începerii campionatului mondial, modulo 666013.
h2. Cerinţă
Cunoscând numărul de oraşe $N$, modul în care acestea sunt conectate, numărul de carteluri iniţiale $K$ şi cele $K$ oraşe în care se află cartelurile, să se determine numărul de moduri în care ţara poate fi împărţită între cartelurile de cafea, modulo $666013$.
Cunoscând numărul de oraşe N, modul în care acestea sunt conectate, numărul de carteluri iniţiale K şi cele K oraşe în care se află cartelurile, să se determine numărul de moduri în care ţara poate fi împărţită între cartelurile de cafea, modulo 666013.
h2. Date de intrare
Fişierul de intrare $karb2.in$ conţine pe prima linie $2$ numere naturale $N$ şi $K$, reprezentând numărul de oraşe, respectiv numărul cartelurilor existente iniţial. Pe a doua linie din fişier se vor afla $K$ numere, reprezentând oraşele în care se află cele $K$ carteluri. Pe următoarele $N-1$ linii se vor afla câte două numere naturale, reprezentând o legătură între cele două oraşe.
Fişierul de intrare $karb2.in$ conţine pe prima linie 2 numere naturale N şi K, reprezentând numărul de oraşe, respectiv numărul cartelurilor existente iniţial. Pe a doua linie din fişier se vor afla K numere, reprezentând oraşele în care se află cele K carteluri. Pe următoarele N-1 linii se vor afla câte două numere naturale, reprezentând o legătură între cele două oraşe.
h2. Date de ieşire
Pe prima linie a fişierului de ieşire $karb.out$ se va scrie un singur număr natural reprezentând numărul de moduri modulo $666013$.
Pe prima linie a fişierului de ieşire karb.out se va scrie un singur număr natural reprezentând numărul de moduri modulo 666013.
h2. Restricţii
* $1 ≤ K ≤ N ≤ 100 000$
* Pentru teste în valoare de $10%$ din punctaj se garantează că $KN ≤ 7$,
iar pentru alte $20%$ din teste se garantează că $k = 2$.
* 1 ≤ K ≤ N ≤ 100 000
* Pentru teste în valoare de 10% din punctaj se garantează că kn ≤ 7,
iar pentru alte 20% din teste se garantează că k = 2.
* Două oraşe sunt vecine dacă există o stradă bidirecţională între ele.
h2. Exemplu

Nu exista diferente intre securitate.

Diferente intre topic forum:

9927