Jaś i jego klawiatura - zadanie kombinatoryczne

Mam problem z tym zadaniem: http://ki.staszic.waw.pl/task.php?name=klawiatura2
Wiem, że rozwiązanie polega na wykorzystaniu programowania dynamicznego, ale nigdy nie robiłem zadań kombinatorycznych wymagających użycia DP (no może poza obliczaniem n po k za pomocą trójkąta pascala), więc nie mam pomysłu.

Jeżeli masz tylko 1 literę hasła to może ono się kończyć na każdą z 26 liter i na każdą z nich jest tylko jeden wariant.
Czyli masz 26-elementową tablicę wypełnioną jedynkami.
Całkowita ilość wariantów to suma elementów tej tablicy.
Teraz zastanawiamy się nad dwuliterowym hasłem - zerujesz drugą 26-elementową tablicę i dla każdej litery w pierwszej odpowiednio zwiększasz komórki w drugiej.
Po zakończeniu wypełnienia kopiujesz wynik do pierwszej tablicy i zerujesz drugą.
itd.

Zapisujemy to w postaci macierzy:
Dla:

a b
b c
c a
unsigned long long M[26][26]=
   {
      {1,1,0, ...},
      {0,1,1, ...},
      {1,0,1, ...},
      ...
   };

Mnożymy to poprzez jedynkową kolumnę bool V[26]={1,1,1,1, ... 1};
Dla dwuliterowego - MV
Dla trzyliterowego - M(M*V)
Dal N literowego M^(N-1)*V
Trzeba zastosować szybkie potęgowanie:

Mógłbyś jaśniej opisać co trzeba zrobić po obliczeniu M^(N-1) * V? Pierwszą część, czyli sposób gdzie się liniowo wypełnia tablicę na podstawie drugiej rozumiem, ale tego co robisz z macierzami już nie ogarniam.

Zsumować komórki wyniku.

Po zsumowaniu komórek tablicy M^(N-1) * V dla danych:
3 4
a b
b c
c a
f g
otrzymuję liczbę 37. Co ta liczba ma wspólnego z wynikiem, który wynosi w tym przypadku 17371?

Coś źle liczysz, po zsumowaniu komórek tablicy M^(N-1) * V dla danych:

3 4
a b
b c
c a
f g

otrzymujesz liczbę: 17371

Poprawiłem, nie zauważyłem poprawionej pierwszej liczby.

Pokaż kod, lub przynajmniej pośrednie wyniki:

1. wypełnioną macierz M
2. policzoną macierz M²
3. policzoną macierz M² * M

To jak wypełniasz tablicę M za pierwszym razem? (Jak juz mówiłem, nie wiem co jest liczone w tych macierzach, rozumiem tylko ten pierwszy liniowy sposób)

Wypełnienie macierzy masz w przykładzie do pierwszego postu.
Podaj kod lub wyniki pośrednie lub zgłoś się na forum wróżbitów.

1. V (twoje W) to musi być kolumna (nie macierz)
2. W obliczeniu M^(n-1) (twoje A) ma brać udział M, skąd ci się tam przyplątało V nie mam pojęcia
3. Nie stosuj i++ tam gdzie możesz zastosować ++i - niejednokrotnie ci się ten brzydki nawyk zemści.
4. Stosuj indeksacje od 0 bo to for(int i = 1; i <= k; i++) znacznie łatwiejsze w zrozumieniu w postaci for(int i=0;i<k;++i)
5. Nazywaj zmienne sensownie, bo nazwanie a,b spowodowało że pomyliłeś co jest w pionie a co w poziomie, to samo z nazewnictwem i,j,l (dwa błędy)
6. Zapoznaj się z operacjami bitowymi & i >> ponieważ są znacznie szybsze niż % i /

1. Macierz M[y][x] oznacza że po literce x może pojawić się literka y
2. Cały ten kod da się zapisać w 40 wierszy (o ile po ludzku zapisywać)