h2. bridge

Un algoritm de complexitate $O(M + N * K)$ folosind programarea dinamica nu este foarte greu de gasit. Daca notam cu $M{~i,j~}$ numarul de moduri (modulo $666013$) de a ajunge in $i$ pasi pe scandura $j$ din pozitia initiala, atunci mai trebuie avut grija doar la relatiile de recurenta. In cazul de fata vom utiliza metoda inainte si vom trata cazurile: daca scandura $j$ este lipsa atunci $M{~i,j~} = 0$, daca scandura $j$ este teleportoare incrementam $M{~i+1,unde[j]~}$ cu $M{~i,j~}$ daca si numai daca {$unde[j]$} nu este lipsa sau subreda ({$unde[j]$} este destinatia teleportarii de pe scandura $j$),daca $j$ este scandura buna, incrementam $M{~i+1,j+1~}$ cu $M{~i,j~}$ si $M{~i+1,j+2~}$ cu $M{~i,j~}$ doar daca $j+2$ nu e lipsa sau subreda, etc.

Un algoritm de complexitate $O(M + N * K)$ folosind programarea dinamica nu este foarte greu de gasit. Daca notam cu $M{~i,j~}$ numarul de moduri (modulo $666013$) de a ajunge in $i$ pasi pe scandura $j$ din pozitia initiala, atunci mai trebuie avut grija doar la relatiile de recurenta. In cazul de fata vom utiliza metoda inainte si vom trata cazurile: daca scandura $j$ este lipsa atunci $M{~i,j~} = 0$, daca scandura $j$ este teleportoare incrementam $M{~i+1,unde{~j~}~}$ cu $M{~i,j~}$ daca si numai daca {$unde{~j~}$} nu este lipsa sau subreda ({$unde{~j~}$} este destinatia teleportarii de pe scandura $j$),daca $j$ este scandura buna, incrementam $M{~i+1,j+1~}$ cu $M{~i,j~}$ si $M{~i+1,j+2~}$ cu $M{~i,j~}$ doar daca $j+2$ nu e lipsa sau subreda, etc.

Avand construita matricea $M$, pentru fiecare query putem raspunde acum in $O(1)$. Exista diferite optimizari care pot fi facute si care sporesc substantial timpul de executie.