Amistats difícils de comptar

Enviar solució
Punts: 7
Temps Límit: 0.5s
Límit de memòria: 64M
Autor/a:
perePro
tipus del problema
Pensar!
Categoria
Lliga de Programació FP
Llenguatges permesos
C#, C++, Haskell, Java, Kotlin, PHP, Python

Graf d'amistats En Joan és molt aficionat a fer problemes de programació competitiva en plataformes com JO-EL , Acepta el reto o Codeforces, entre d’altres. En aquestes plataformes, ben aviat es va adonar que cal anar molt amb compte amb el temps d’execució de les solucions que es proposen. A vegades la solució sembla senzilla fent un bucle que s'executa en temps lineal. Aquest temps, però, no és acceptable si es pot substituir per una fórmula, que no té per què ser complicada, i calcula el valor desitjat en temps constant.

També va adonar-se que quan els números són grans aquestes plataformes no admeten solucions de temps lineal si es pot resoldre en temps logarítmic. Per exemple,

  • \(2^{16}\) es pot calcular en temps lineal fent \(15\) productes, \((2·2·2·2·2·2·2·2·2·2·2·2·2·2·2·2)\), o es pot fer en temps logarítmic fent \(4\) productes, \({({({(2^2)}^2)}^2)}^2\).
  • \(2^{19}\) es pot calcular amb 6 productes, \(2^{16} · 2^2 · 2\). Per a fer aquests càlculs, us pot ajudar saber que \(19\) en binari és \(10011\).
  • \(2^{1048576}\) es pot calcular amb només 20 productes en comptes de fer-ho amb \(1048576\). (Notem que \(1048576\) és igual a \(2^{20}\)).

Finalment, va veure que quan el resultat és un enter molt gran moltes vegades demanen una solució mòdul \(10^9 + 7\). D’aquesta manera, el resultat passa a ser un enter de com a molt \(32\) dos bits, que és de tipus bàsic en C, C++, Java o C#, i no cal fer servir enters grans com fa, per exemple, el Python (utilitzant biblioteques de C).

Tenint en compte tots aquests aspectes, va plantejar el següent problema.

Comptem amics

En una coneguda xarxa social els usuaris es fan amics entre ells. L’objectiu és calcular de quantes maneres diferents poden tenir relacions d’amistat un nombre concret d’usuaris d’aquesta xarxa. Com que el nombre de possibilitats creix molt ràpidament, es demana que la solució que es doni sigui mòdul \(10^9 + 7\).

Per exemple, si la xarxa és de \(2\) persones, l’Anna i la Berta, hi ha dues possibilitats. Que l’Anna i en Berta siguin amigues o que no ho siguin.

Si a la xarxa hi ha tres persones, l’Anna (A), la Berta (B) i en Carles (C) hi ha 8 possibilitats.

  1. Cap d’elles és amiga de cap altra
  2. Anna amiga de la Berta: (A,B)
  3. Anna amiga del Carles: (A,C)
  4. Berta amiga del Carles: (B,C)
  5. (A,B) i (A,C)
  6. (A,B) i (B,C)
  7. (A,C) i (B,C)
  8. (A,B), (A,C) i (B,C). Totes les persones són amigues entre elles.

Fixem-nos que si fem servir un 1 per indicar que dues persones són amigues i un 0 per indicar que no ho són, podem etiquetar tots els casos anteriors amb 3 bits. Per exemple, \(111\) etiqueta el cas (A,B), (A,C) i (B,C), \(100\) etiqueta el cas (A,B) i \(000\) el cas en què no hi ha cap amistat.

Entrada

La primera línia indica el nombre de casos a considerar. Cada cas està en una línia i conté el nombre de persones que es poden relacionar a la xarxa. (un nombre enter \(n\), \(2 \leq n \leq 2000000000\))

Sortida

La sortida de cada cas és un enter amb el nombre de maneres de relacionar-se les \(n\) persones \(\mod 10^9 + 7\).

Exemple d'entrada

5
2
3
4
5
1000

Exemple de sortida

2
8
64
1024
229176128

Comentaris


  • 0
    perePro  comentat a les gen. 30, 2026, 9:31 a.m. ← editat

    Aquest exercici és molt més senzill del que sembla i està més pensat per distingir de manera pràctica entre \(O(n)\) i \(O(\log(n))\) com a exemple de complexitat algorísmica

    Algunes pistes:

    • \(6 + 5 + 4 + 3 + 2 + 1 = (6 + 1) + (5 + 2) + (4 + 3) = 7 + 7 + 7\)
    • \((x \times y) \mod n = ((x \mod n) \times (y \mod n)) \mod n\)

    I I la pista definitiva per calcular \(2^n\)

    • \(2^{2} = 2\times2\)
    • \(2^{4} = 2^2 \times 2^2\)
    • \(2^{8} = 2^4 \times 2^4\)
    • \(2^{16} = 2^8 \times 2^8\)
    • \(2^{19} = 2^{16} \times 2^{2} \times 2\)