RSS Feed
Precedenta

Problema 408

29 Decembrie 2012

Căi admisibile printr-o matrice


O să numim un punct (x, y) inadmisibil dacă numerele întregi x, y și x + y sunt toate pătrate perfecte pozitive.
De exemplu, (9, 16) e inadmisibil, în timp ce punctele (0, 4), (3, 1) și (9, 4) nu sunt.

Fie o cale de la punctul (x1, y1) la punctul (x2, y2) folosind doar pași unitari spre nord sau est.
O să numim o astfel de cale admisibilă dacă nici unul din punctele prin care trece nu e inadmisibil.

Fie P(n) numărul de căi admisibile de la (0, 0) la (n, n).
Se poate verifica că P(5) = 252, P(16) = 596994440 și P(1000) mod 1 000 000 007 = 341920854.

Găsește P(10 000 000) mod 1 000 000 007.


>> Vezi problema originală <<