El problema "El Dilema del Vigía" (Vijos 1067) nos presenta un escenario inspirado en Warcraft III, donde un personaje llamado Vigía (Warden) debe inspeccionar una serie de prisiones alineadas. El Vigía comienza en la entrada y debe finalizar en la última prisión (la número n). Su habilidad especial, "Parpadeo" (Blink), le permite saltar hacia adelante un número de prisiones determinado por el nivel de su habilidad, k. Es decir, con una habilidad de nivel k, puede saltar como máximo k prisiones hacia adelante.

El objetivo es determinar la cantidad total de caminos posibles que el Vigía puede tomar para llegar a la prisión n, partiendo de la entrada, sin retroceder y sin necesidad de visitar todas las prisiones intermedias. Dado que el número de combinaciones puede ser muy grande, se solicita la respuesta módulo 7777777.

Análisis del Problema y Deducción de la Recurrencia

Consideremos primero el caso con k=2. El Vigía puede saltar 1 o 2 prisiones hacia adelante. Si f(n) representa el número de formas de llegar a la prisión n, entonces para llegar a n, el Vigía pudo haber estado en n-1 (y saltó 1 prisión) o en n-2 (y saltó 2 prisiones). Esto nos lleva a la recurrencia: f(n) = f(n-1) + f(n-2), que es la famosa sucesión de Fibonacci. Las condiciones iniciales serían f(0) = 1 (una forma de estar en la "prisión 0", el inicio) y f(1) = 1 (una forma de llegar a la prisión 1 desde el inicio). Si cnosideramos la primera prisión como la 1, entonces f(1)=1, f(2)=2 (1->2, 2). Usando la notación de la 0-indexed, f(0)=1, f(1)=1, f(2)=2, f(3)=3, f(4)=5.

Generalizando para un nivel de habilidad k, el Vigía puede saltar 1, 2, ..., hasta k prisiones. Por lo tanto, para llegar a la prisión n, el Vigía pudo haber estado en n-1, n-2, ..., o n-k. La recurrencia se expande a: f(n) = f(n-1) + f(n-2) + ... + f(n-k).

Manejo de Casos Especiales y Condiciones Iniciales

Si el número de prisiones n es menor que la capacidad máxima de salto k, la recurrencia se adapta. Para k > n, el Vigía, en lugar de poder saltar hasta k prisiones, solo puede saltar hasta n prisiones. La recurrencia se convierte en: f(n) = f(n-1) + f(n-2) + ... + f(0).

Considerando la definición para f(n) = f(n-1) + ... + f(n-k), si tenemos f(n-1) = f(n-2) + ... + f(n-k-1), entonces f(n) = f(n-1) + f(n-1) - f(n-k-1) = 2*f(n-1) - f(n-k-1). Esta forma simplificada es útil para reducir la complejidad.

Las condiciones iniciales para la recurrencia generalizada f(n) = f(n-1) + ... + f(n-k) son: f(0) = 1 (representando el punto de partida) f(1) = 1 f(2) = 2 (1->2, 2) ... f(i) = f(i-1) + ... + f(0) para 1 <= i < k. Esto es equivalente a f(i) = 2^(i-1) para 1 <= i < k.

Aceleración Matricial

La recurrencia f(n) = f(n-1) + f(n-2) + ... + f(n-k) puede ser expresada en forma matricial. Para ello, necesitamos un vector de estado que contenga los k valores previos necesarios para calcular el siguiente. Nuestro vector de estado podría ser: V(n) = [f(n), f(n-1), ..., f(n-k+1)]^T

La matriz de transición T debe cumplir la relación V(n) = T * V(n-1). Para k=2 (Fibonacci): [f(n), f(n-1)]^T = [[1, 1], [1, 0]] * [f(n-1), f(n-2)]^T

Para el caso general k: La matriz de transición T de tamaño k x k será: La primera fila contendrá [1, 1, ..., 1] (coeficientes de la recurrencia). Las siguientes k-1 filas contendrán un 1 en la sub-diagonal y 0s en el resto, para desplazar los valores: T = [[1, 1, 1, ..., 1], [1, 0, 0, ..., 0], [0, 1, 0, ..., 0], ..., [0, 0, ..., 1, 0]]

Si queremos calcular f(n), necesitamos elevar la matriz T a la potencia n-k+1 (o similar, dependiendo de la indexación y el vector inicial) y multiplicarla por un vector de estado inicial. Por ejemplo, si nuestro vector inicial es V(k-1) = [f(k-1), f(k-2), ..., f(0)]^T, entonces V(n) = T^(n-(k-1)) * V(k-1).

El vector inicial V(k-1) contendrá los valores calculados previamente: V(k-1) = [2^(k-2), 2^(k-3), ..., 1, 1]^T (asumiendo f(0)=1).

Implementación con Código

La implementación involucra definir una estructura para la matriz, métodos para multiplicación de matrices y exponenciación por cuadratura (para calcular T^p eficientemente en tiempo logarítmico). La construcción de la matriz de transición y el vector inicial debe hacerse con cuidado según las condiciones iniciales y la recurrencia.

El código proporcionado maneja esto definiendo la estructura Matrix con operaciones de multiplicación y potenciación. La función pre1(k) construye la matriz de transición T de tamaño k x k. La función pre2(k) (aunque su nombre sugiere otra cosa) parece inicializar un vector base para los cálculos. La multiplicación matricial se realiza módulo 7777777.

El proceso principal en main es:

1. Leer k y n.
2. Inicializar el vector de estado base A (con las condiciones iniciales f(0) a f(k-1)).
3. Construir la matriz de transición B de tamaño k x k.
4. Calcular B^(n-k) usando exponenciación matricial.
5. Multiplicar el vector inicial A por la matriz resultante B.
6. El elemento final (generalmente A.c[1][k] o similar, dependiendo de cómo se estructure el vector resultante) contendrá el valor de f(n) módulo 7777777.

Es crucial notar que la indexación en el código y la forma en que se manejan las potencias de la matriz y el vector inicial deben alinearse correctamente con la definición de la recurrencia y las condiciones iniciales.

Ejemplo de Construcción Matricial (k=3):

Recurrencia: f(n) = f(n-1) + f(n-2) + f(n-3).

Vector de estado: [f(n), f(n-1), f(n-2)]^T.

Matriz de transición (T):

   [[1, 1, 1],
    [1, 0, 0],
    [0, 1, 0]]
   

Si el vector inicial es [f(2), f(1), f(0)]^T (asumiendo f(0)=1, f(1)=1, f(2)=2), entonces para obtener f(n), necesitaríamos calcular T^(n-2) * [f(2), f(1), f(0)]^T.

El código implementa una lógica similar, donde la matriz de transición se construye y luego se eleva a la potencia necesaria. El resultado final se extrae de la multiplicación del vector inicial por la matriz transformada.

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
  
#define MAX_K 20 // Límite superior para k en la matriz
#define MOD 7777777

typedef long long ll;

ll K, N; // k: nivel de habilidad, n: número de prisiones

struct Matrix {
   ll dim; // Dimensión de la matriz (k x k)
   ll mat[MAX_K][MAX_K];

   Matrix(ll d = 0) : dim(d) {
       memset(mat, 0, sizeof(mat));
   }

   // Multiplica dos matrices, resultando en 'this'
   Matrix operator*(const Matrix& other) const {
       Matrix result(dim);
       for (ll i = 0; i < dim; ++i) {
           for (ll j = 0; j < dim; ++j) {
               for (ll l = 0; l < dim; ++l) {
                   result.mat[i][j] = (result.mat[i][j] + (mat[i][l] * other.mat[l][j]) % MOD) % MOD;
               }
           }
       }
       return result;
   }

   // Calcula la matriz elevada a una potencia usando exponenciación por cuadratura
   Matrix power(ll exp) const {
       Matrix base = *this;
       Matrix result(dim);
       for (ll i = 0; i < dim; ++i) result.mat[i][i] = 1; // Matriz identidad

       while (exp > 0) {
           if (exp % 2 == 1) result = result * base;
           base = base * base;
           exp /= 2;
       }
       return result;
   }
};

// Construye la matriz de transición para la recurrencia
Matrix build_transition_matrix(ll k) {
   Matrix T(k);
   // Primera fila: coeficientes de la recurrencia (todos 1)
   for (ll j = 0; j < k; ++j) {
       T.mat[0][j] = 1;
   }
   // Sub-diagonal: para el desplazamiento de los estados
   for (ll i = 1; i < k; ++i) {
       T.mat[i][i - 1] = 1;
   }
   return T;
}

int main() {
   cin >> K >> N;

   // Caso base: si N es pequeño, el cálculo directo es posible y más simple.
   // Sin embargo, para N muy grande, necesitamos la aceleración matricial.
   // Consideramos N como el número de pasos a dar desde el inicio.
   // Si N=1, hay 1 forma (trivial). Si N=2 (con k>=2), hay 2 formas.
   // Si N <= K, la formula f(n) = 2^(n-1) para n>0, f(0)=1 se aplica.
   
   if (N == 0) { // Caso especial si N pudiera ser 0, aunque el problema dice N>=1
       cout << 1 << endl;
       return 0;
   }
   if (N < K) {
       // Calculamos f(N) = f(N-1) + ... + f(0)
       // f(0)=1, f(1)=1, f(2)=2, f(3)=3, f(4)=5 (si k>=4)
       // f(n) = 2^(n-1) para 1 <= n < K
       ll result = 1; // Para f(1)
       for (ll i = 2; i <= N; ++i) {
           result = (result * 2) % MOD;
       }
       cout << result << endl;
       return 0;
   }
   
   // Para N >= K, usamos aceleración matricial.
   // Definimos la recurrencia: f(n) = sum_{i=1 to k} f(n-i)
   // Vector de estado: [f(n), f(n-1), ..., f(n-k+1)]^T
   // Matriz de transición T (k x k)

   Matrix T = build_transition_matrix(K);

   // Elevamos T a la potencia N-K+1 para obtener el estado f(N)
   // desde el estado inicial [f(K-1), f(K-2), ..., f(0)]
   // Las condiciones iniciales son:
   // f(0) = 1
   // f(i) = 2^(i-1) para 1 <= i < K

   Matrix T_pow = T.power(N - K); // Potencia para transformar el vector de estado f(K-1)...f(0) a f(N)...f(N-K+1)

   // El resultado f(N) se obtiene multiplicando la primera fila de T_pow
   // por el vector de condiciones iniciales [f(K-1), ..., f(0)]
   
   ll final_result = 0;
   // Calculamos las condiciones iniciales f(0) a f(K-1)
   ll initial_states[MAX_K];
   initial_states[0] = 1; // f(0)
   ll current_power_of_2 = 1; // Para 2^(i-1)
   for (ll i = 1; i < K; ++i) {
       initial_states[i] = current_power_of_2;
       current_power_of_2 = (current_power_of_2 * 2) % MOD;
   }
   
   // La primera fila de T_pow contiene los coeficientes para calcular f(N)
   // f(N) = T_pow[0][0]*f(K-1) + T_pow[0][1]*f(K-2) + ... + T_pow[0][K-1]*f(0)
   for (ll j = 0; j < K; ++j) {
       final_result = (final_result + (T_pow.mat[0][j] * initial_states[K - 1 - j]) % MOD) % MOD;
   }

   cout << final_result << endl;

   return 0;
}