Dados dos números enteros N , M que denotan N×M tablero de ajedrez, la tarea es contar el número de formas en que un caballo puede llegar a (N, M) a partir de (0, 0) . Dado que la respuesta puede ser muy grande, imprima la respuesta módulo 10 9 +7 .
Ejemplo:
Entrada: N =3, M= 3
Salida: 2
Explicación: Las
dos formas de llegar a (3, 3) desde (0, 0) son las siguientes:
(0, 0) → (1, 2) → (3, 3)
(0, 0) → (2, 1) → (3, 3)
Entrada: N=4, M=3
Salida: 0
Explicación: No existe forma posible de llegar a (4, 3) desde (0, 0).
Enfoque : la idea aquí es observar el patrón de que cada movimiento incrementa el valor de la coordenada x + el valor de la coordenada y en 3. Siga los pasos a continuación para resolver el problema.
- Si (N + M) no es divisible por 3 , entonces no existe ningún camino posible.
- Si (N + M) % 3==0 , cuente el número de movimientos de tipo (+1, +2) , es decir, X y cuente el número de movimientos de tipo (+2, +1) , es decir, Y.
- Encuentre la ecuación del tipo (+1, +2) es decir , X + 2Y = N
- Encuentre la ecuación del tipo (+2, +1) es decir , 2X + Y = M
- Encuentre los valores calculados de X e Y , si X < 0 o Y < 0 , entonces no existe una ruta posible.
- De lo contrario, calcule ( X+Y ) C Y .
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ Program to implement // the above approach #include <bits/stdc++.h> using namespace std; const int Mod = 1e9 + 7; // Function to return X^Y % Mod int power(int X, int Y, int Mod) { // Base Case if (Y == 0) return 1; int p = power(X, Y / 2, Mod) % Mod; p = (p * p) % Mod; if (Y & 1) { p = (X * p) % Mod; } return p; } // Function to return the // inverse of factorial of N int Inversefactorial(int N) { // Base case if (N <= 0) return 1; int fact = 1; for (int i = 1; i <= N; i++) { fact = (fact * i) % Mod; } return power(fact, Mod - 2, Mod); } // Function to return factorial // of n % Mod int factorial(int N) { // Base case if (N <= 0) return 1; int fact = 1; for (int i = 1; i <= N; i++) { fact = (fact * i) % Mod; } return fact; } // Function to return the value // of n! / (( n- k)! * k!) int nck(int N, int K) { int factN = factorial(N); int inv = Inversefactorial(K); int invFact = Inversefactorial(N - K); return (((factN * inv) % Mod) * invFact) % Mod; } // Function to return the count of // ways to reach (n, m) from (0, 0) int TotalWaYs(int N, int M) { // If (N + M) % 3 != 0 if ((N + M) % 3 != 0) // No possible way exists return 0; // Calculate X and Y from the // equations X + 2Y = N // and 2X + Y == M int X = N - (N + M) / 3; int Y = M - (N + M) / 3; if (X < 0 || Y < 0) return 0; return nck(X + Y, Y); } // Driver Code int main() { int N = 3, M = 3; cout << TotalWaYs(N, M); return 0; }
Java
// Java Program to implement // the above approach import java.util.*; class GFG{ static int Mod = (int) (1e9 + 7); // Function to return X^Y % Mod static int power(int X, int Y, int Mod) { // Base Case if (Y == 0) return 1; int p = power(X, Y / 2, Mod) % Mod; p = (p * p) % Mod; if ((Y & 1) != 0) { p = (X * p) % Mod; } return p; } // Function to return the // inverse of factorial of N static int Inversefactorial(int N) { // Base case if (N <= 0) return 1; int fact = 1; for (int i = 1; i <= N; i++) { fact = (fact * i) % Mod; } return power(fact, Mod - 2, Mod); } // Function to return factorial // of n % Mod static int factorial(int N) { // Base case if (N <= 0) return 1; int fact = 1; for (int i = 1; i <= N; i++) { fact = (fact * i) % Mod; } return fact; } // Function to return the value // of n! / (( n- k)! * k!) static int nck(int N, int K) { int factN = factorial(N); int inv = Inversefactorial(K); int invFact = Inversefactorial(N - K); return (((factN * inv) % Mod) * invFact) % Mod; } // Function to return the count of // ways to reach (n, m) from (0, 0) static int TotalWaYs(int N, int M) { // If (N + M) % 3 != 0 if (((N + M) % 3 )!= 0) // No possible way exists return 0; // Calculate X and Y from the // equations X + 2Y = N // and 2X + Y == M int X = N - (N + M) / 3; int Y = M - (N + M) / 3; if (X < 0 || Y < 0) return 0; return nck(X + Y, Y); } // Driver Code public static void main(String[] args) { int N = 3, M = 3; System.out.print(TotalWaYs(N, M)); } } // This code is contributed by Rohit_ranjan
Python3
# Python3 program to implement # above approach Mod = int(1e9 + 7) # Function to return X^Y % Mod def power(X, Y, Mod): # Base case if Y == 0: return 1 p = power(X, Y // 2, Mod) % Mod p = (p * p) % Mod if Y & 1: p = (X * p) % Mod return p # Function to return the # inverse of factorial of N def Inversefactorial(N): # Base case if N <= 0: return 1 fact = 1 for i in range(1, N + 1): fact = (fact * i) % Mod return power(fact, Mod - 2, Mod) # Function to return factorial # of n % Mod def factorial(N): # Base case if N <= 0: return 1 fact = 1 for i in range(1, N + 1): fact = (fact * i) % Mod return fact # Function to return the value # of n! / (( n- k)! * k!) def nck(N, K): factN = factorial(N) inv = Inversefactorial(K) invFact = Inversefactorial(N - K) return (((factN * inv) % Mod) * invFact) % Mod # Function to return the count of # ways to reach (n, m) from (0, 0) def TotalWays(N, M): # If (N + M) % 3 != 0 if (N + M) % 3 != 0: # No possible way exists return 0 # Calculate X and Y from the # equations X + 2Y = N # and 2X + Y == M X = N - (N + M) // 3 Y = M - (N + M) // 3 if X < 0 or Y < 0: return 0 return nck(X + Y, Y) # Driver code N, M = 3, 3 print(TotalWays(N, M)) # This code is contributed by Stuti Pathak
C#
// C# program to implement // the above approach using System; class GFG{ static int Mod = (int)(1e9 + 7); // Function to return X^Y % Mod static int power(int X, int Y, int Mod) { // Base Case if (Y == 0) return 1; int p = power(X, Y / 2, Mod) % Mod; p = (p * p) % Mod; if ((Y & 1) != 0) { p = (X * p) % Mod; } return p; } // Function to return the // inverse of factorial of N static int Inversefactorial(int N) { // Base case if (N <= 0) return 1; int fact = 1; for(int i = 1; i <= N; i++) { fact = (fact * i) % Mod; } return power(fact, Mod - 2, Mod); } // Function to return factorial // of n % Mod static int factorial(int N) { // Base case if (N <= 0) return 1; int fact = 1; for(int i = 1; i <= N; i++) { fact = (fact * i) % Mod; } return fact; } // Function to return the value // of n! / (( n- k)! * k!) static int nck(int N, int K) { int factN = factorial(N); int inv = Inversefactorial(K); int invFact = Inversefactorial(N - K); return (((factN * inv) % Mod) * invFact) % Mod; } // Function to return the count of // ways to reach (n, m) from (0, 0) static int TotalWaYs(int N, int M) { // If (N + M) % 3 != 0 if (((N + M) % 3 ) != 0) // No possible way exists return 0; // Calculate X and Y from the // equations X + 2Y = N // and 2X + Y == M int X = N - (N + M) / 3; int Y = M - (N + M) / 3; if (X < 0 || Y < 0) return 0; return nck(X + Y, Y); } // Driver Code public static void Main(String[] args) { int N = 3, M = 3; Console.Write(TotalWaYs(N, M)); } } // This code is contributed by Amit Katiyar
Javascript
<script> // Javascript Program to implement // the above approach var Mod = 1000000007; // Function to return X^Y % Mod function power(X, Y, Mod) { // Base Case if (Y == 0) return 1; var p = power(X, Y / 2, Mod) % Mod; p = (p * p) % Mod; if (Y & 1) { p = (X * p) % Mod; } return p; } // Function to return the // inverse of factorial of N function Inversefactorial(N) { // Base case if (N <= 0) return 1; var fact = 1; for (var i = 1; i <= N; i++) { fact = (fact * i) % Mod; } return power(fact, Mod - 2, Mod); } // Function to return factorial // of n % Mod function factorial(N) { // Base case if (N <= 0) return 1; var fact = 1; for (var i = 1; i <= N; i++) { fact = (fact * i) % Mod; } return fact; } // Function to return the value // of n! / (( n- k)! * k!) function nck( N, K) { var factN = factorial(N); var inv = Inversefactorial(K); var invFact = Inversefactorial(N - K); return (((factN * inv) % Mod) * invFact) % Mod; } // Function to return the count of // ways to reach (n, m) from (0, 0) function TotalWaYs(N, M) { // If (N + M) % 3 != 0 if ((N + M) % 3 != 0) // No possible way exists return 0; // Calculate X and Y from the // equations X + 2Y = N // and 2X + Y == M var X = N - (N + M) / 3; var Y = M - (N + M) / 3; if (X < 0 || Y < 0) return 0; return nck(X + Y, Y); } // Driver Code var N = 3, M = 3; document.write( TotalWaYs(N, M)); </script>
2
Complejidad temporal: O(X + Y + log(mod)).
Espacio Auxiliar: O(1)