Nombre de particions P14519
El curs acadèmic 2024-2025 de la FME s’ha dedicat al matemàtic hindú Srinivasa Ramanujan qui, entre d’altres problemes, va estudiar la funció p(n) que retorna el nombre de particions d’un nombre natural n donat. És a dir, p(n) és el nombre de maneres d’escriure n com a suma de naturals (estrictament positius), sense tenir en compte l’ordre dels sumands.
Per exemple, p(4) = 5, perquè el 4 es pot escriure de cinc maneres diferents:
| 4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1 . |
Fixeu-vos que considerem 1 + 3 i 3 + 1 com la mateixa suma, i igualment amb 1 + 1 + 2, 1 + 2 + 1 i 2 + 1 + 1.
Com un altre exemple, p(5) = 7, perquè el 5 es pot escriure de set maneres diferents:
| 5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1 . |
Podeu calcular p(n)?
Entrada
L’entrada consisteix en diversos casos, cadascun amb una n entre 1 i 1000. Els jocs de proves privats tenen molts nombres, possiblement repetits.
Sortida
Per a cada n, escriviu p(n) mòdul 108 + 7.
Input
4 5 1 2 3 10 1000
Output
5 7 1 2 3 42 57246495
- Author
- Enric Rodríguez
- Language
- Catalan
- Official solutions
- C++
- User solutions
- C++