| Fişierul intrare/ieşire: | influencer.in, influencer.out | Sursă | ONI 2026, Baraj Seniori, ziua 1 |
| Autor | Alexandru Lorintz | Adăugată de |  Ivan Andrei •IvanAndrei |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Influencer
Reţeaua socială Circle are N influenceri, numerotaţi de la 0 la N - 1, aşezaţi sub forma unui cerc. În interiorul reţelei există M legături speciale de comunicare bidirecţională, date sub forma unor perechi (u, v). Aceste legături respectă o regulă strictă de securitate: dacă desenăm influencerii pe cerc şi legăturile ca segmente (corzi) între ei, oricare două segmente nu se pot intersecta decât, eventual, în capete. De asemenea, legăturile speciale se pot forma doar între influenceri neadiacenţi pe cerc.
CEO-ul reţelei doreşte să configureze conexiunile de bază de pe conturul cercului. Pentru fiecare pereche de influenceri adiacenţi i şi (i + 1) % N (unde 0 ≤ i ≤ N - 1), se alege un tip de conexiune, reprezentat printr-un caracter dintr-un şir de configurare S de lungime N (indexat de la 0). Caracterul Si poate fi:
- N: Nu există comunicare directă între i şi (i + 1) % N.
- L: Comunicare directă unidirecţională de la (i + 1) % N la i.
- R: Comunicare directă unidirecţională de la i la (i + 1) % N.
- B: Comunicare directă bidirecţională între i şi (i + 1) % N.
Cerinţă
Să se determine numărul de moduri distincte de a construi şirul de configurare S astfel încât în reţeaua rezultată, orice influencer să poată transmite un mesaj oricărui alt influencer, direct sau indirect, folosind conexiunile de pe cerc şi legăturile speciale. Deoarece acest număr poate fi foarte mare, se cere afişarea lui modulo 109 + 7.
Date de intrare
Fişierul de intrare influencer.in conţine pe prima linie două numere naturale N şi M, separate printr-un spaţiu. Pe următoarele M linii se vor afla câte două numere naturale u şi v, separate printr-un spaţiu, reprezentând o legătură specială bidirecţională între influencerul u şi v.
Date de ieşire
Fişierul de ieşire influencer.out va conţine pe o singură linie un număr natural, reprezentând numărul de şiruri de configurare S valide, modulo 109 + 7.
Restricţii
- 3 ≤ N ≤ 1 000 000
- 0 ≤ M ≤ [N/2], unde [x] reprezintă parte întreagă din x
- Pentru orice legătură specială (u, v), se garantează că |u - v| ≥ 2 şi perechea nu este (0, N - 1) (nodurile nu sunt adiacente pe cerc).
| # | Punctaj | Restricţii |
|---|---|---|
| 1 | 11 | N ≤ 10 şi corzile nu se pot intersecta în capete |
| 2 | 16 | M = 0 |
| 3 | 9 | M = 1 |
| 4 | 4 | Toate corzile au unul dintre capete în influencerul 0 |
| 5 | 17 | N ≤ 1 000 şi corzile nu se pot intersecta în capete |
| 6 | 29 | Corzile nu se pot intersecta în capete |
| 7 | 14 | Fără alte restricţii |
Exemplu
| influencer.in | influencer.out |
|---|---|
| 4 1 0 2 | 81 |
Explicaţie
Avem N = 4 influenceri şi o singură legătură (M = 1) specială bidirecţională între influencerul 0 şi 2. Această coardă împarte cercul în două jumătăţi care devin independente din punct de vedere al conectivităţii faţă de ansamblul {0, 2}: calea prin utilizatorul 1 şi calea prin utilizatorul 3.
Pentru ca întreaga reţea să fie tare conexă, este suficient şi necesar ca influencerul 1 şi 3 să poată trimite şi primi mesaje de la mulţimea {0, 2}.
Să analizăm muchiile S0 (între 0 şi 1) şi S1 (între 1 şi 2). Există exact 9 perechi de caractere valide care asigură conectivitatea bidirecţională a nodului 1 faţă de {0, 2}:
- BB, BR, BL, BN, RB, RR, LB, LL, NB.
De exemplu, dacă alegem perechea LL (S0 = L, S1 = L), fluxul este 2 → 1 şi 1 → 0. Nodul 1 primeşte de la 2 şi trimite la 0. Deoarece 0 şi 2 comunică direct prin coardă, nodul 1 este perfect integrat în circuit. Orice altă combinaţie (de exemplu NN, RL, LR) va bloca fluxul nodului 1 fie la primire, fie la trimitere.
În mod identic, pentru nodul 3, muchiile de pe cealaltă jumătate a cercului, S2 şi S3, pot fi alese tot în 9 moduri valide.
Deoarece deciziile pentru jumătatea stângă sunt complet independente de cele pentru jumătatea dreaptă (datorită corzii centrale bidirecţionale), numărul total de moduri pentru a construi şirul S este 9 * 9 = 81.
