Dados dos números enteros n y m, donde n representan unos cuadros numerados del 1 al n ym representan unos colores del 1 al m con cantidad ilimitada. La tarea es encontrar el número de formas de pintar las pinturas de manera que no haya dos pinturas consecutivas que tengan los mismos colores.
Nota: La respuesta debe calcularse en módulo 10^9 +7 ya que la respuesta puede ser muy grande.
Ejemplos:
Input: n = 4, m = 2 Output: 2 Input: n = 4, m = 6 Output: 750
Preguntado en: Enfoque de National Instruments :
El número total de color dado es my el total de pinturas es de 1 a n . De acuerdo con la condición de que no haya dos pinturas adyacentes que tengan el mismo color, la primera pintura puede ser pintada por cualquiera de m colores y el resto de cualquier pintura puede ser pintada por cualquiera de m-1 color excepto el color utilizado para la pintura anterior. que. Por lo tanto, si derivamos la solución para el número total de formas,
m * (m-1)^(n-1) es la respuesta real.
Ahora, esto se puede calcular por iteración simple o por el método de cálculo de potencia eficiente en tiempo O (logn) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
#define modd 1000000007
using namespace std;
// Function for finding the power
unsigned long power(unsigned long x,
unsigned long y, unsigned long p)
{
unsigned long res = 1; // Initialize result
x = x % p; // Update x if it is more than or
// equal to p
while (y > 0) {
// If y is odd, multiply x with result
if (y & 1)
res = (res%p * x%p) % p;
// y must be even now
y = y >> 1; // y = y/2
x = (x%p * x%p) % p;
}
return res;
}
// Function to calculate the number of ways
int ways(int n, int m)
{
// Answer must be modulo of 10^9 + 7
return power(m - 1, n - 1, modd) * m % modd;
}
// Driver code
int main()
{
int n = 5, m = 5;
cout << ways(n, m);
return 0;
}
Java
// Java implementation of the above approach
class GFG
{
static final int modd = 1000000007;
// Function for finding the power
static long power(long x, long y, long p)
{
long res = 1; // Initialize result
// Update x if it is more than or
// equal to p
x = x % p;
while (y > 0)
{
// If y is odd, multiply x with result
if (y % 2 == 1)
{
res = (res%p * x%p) % p;
}
// y must be even now
y = y >> 1; // y = y/2
x = (x%p * x%p) % p;
}
return res;
}
// Function to calculate the number of ways
static int ways(int n, int m)
{
// Answer must be modulo of 10^9 + 7
return (int) (power(m - 1, n - 1, modd)
* m % modd);
}
// Driver code
public static void main(String[] args)
{
int n = 5, m = 5;
System.out.println(ways(n, m));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of the # above approach modd = 1000000007 # Function for finding the power def power(x, y, p): res = 1 # Initialize result x = x % p # Update x if it is more # than or equal to p while (y > 0): # If y is odd, multiply x with result if (y & 1): res = (res%p * x%p) % p # y must be even now y = y >> 1 # y = y/2 x = (x%p * x%p) % p return res # Function to calculate the number of ways def ways(n, m): # Answer must be modulo of 10^9 + 7 return power(m - 1, n - 1, modd) * m % modd # Driver code n, m = 5, 5 print(ways(n, m)) # This code is contributed # by Mohit Kumar 29
C#
// C# implementation of the above approach
using System;
class GFG
{
static int modd = 1000000007;
// Function for finding the power
static long power(long x, long y, long p)
{
long res = 1; // Initialize result
// Update x if it is more than or
// equal to p
x = x % p;
while (y > 0)
{
// If y is odd, multiply x with result
if (y % 2 == 1)
{
res = (res%p * x%p) % p;
}
// y must be even now
y = y >> 1; // y = y/2
x = (x%p * x%p) % p;
}
return res;
}
// Function to calculate the number of ways
static int ways(int n, int m)
{
// Answer must be modulo of 10^9 + 7
return (int) (power(m - 1, n - 1, modd)
* m % modd);
}
// Driver code
static public void Main ()
{
int n = 5, m = 5;
Console.WriteLine(ways(n, m));
}
}
// This code is contributed by ajit
PHP
<?php
// PHP implementation of the above approach
// Iterative Function to calculate
// (x^y)%p in O(log y)
function power($x, $y, $p)
{
// Initialize result
$res = 1;
// Update x if it is more
// than or equal to p
$x = $x % $p;
while ($y > 0)
{
// If y is odd, multiply
// x with result
if ($y & 1)
$res = ($res % $p * $x % $p) % $p;
// y must be even now
// y = $y/2
$y = $y >> 1;
$x = ($x % $p * $x % $p) % $p;
}
return $res;
}
// Function to calculate the number of ways
function ways($n, $m)
{
$modd =1000000007;
// Answer must be modulo of 10^9 + 7
return (power($m - 1, $n - 1,
$modd) * $m ) % $modd;
}
// Driver code
$n = 5;
$m = 5;
echo ways($n, $m);
// This code is contributed
// by Arnab Kundu
?>
Javascript
<script>
// Javascript implementation of the above approach
let modd = 1000000007;
// Function for finding the power
function power(x, y, p)
{
let res = 1; // Initialize result
// Update x if it is more than or
// equal to p
x = x % p;
while (y > 0)
{
// If y is odd, multiply x with result
if (y % 2 == 1)
{
res = (res%p * x%p) % p;
}
// y must be even now
y = y >> 1; // y = y/2
x = (x%p * x%p) % p;
}
return res;
}
// Function to calculate the number of ways
function ways(n, m)
{
// Answer must be modulo of 10^9 + 7
return (power(m - 1, n - 1, modd) * m % modd);
}
let n = 5, m = 5;
document.write(ways(n, m));
</script>
1280
Complejidad de Tiempo: O(logN)
Espacio Auxiliar: O(1), ya que no se ha tomado espacio extra.
Publicación traducida automáticamente
Artículo escrito por Shivam.Pradhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA