Dados dos enteros N y M . En cada operación, elija K celdas de una cuadrícula 2D de tamaño N * M y organícelas. Si elegimos las K celdas (x 1 , y 1 ), (x 2 , y 2 ), …, y (x K , y K ) entonces el costo de este arreglo se calcula como ∑ i=1 K-1 ∑ j =i+1 K (|x yo – x j | + |y yo – y j |). La tarea es encontrar la suma de los costos de todos los arreglos posibles de las celdas. La respuesta puede ser muy grande, imprima la respuesta módulo 10 9 + 7
Ejemplos:
Entrada: N = 2, M = 2, K = 2
Salida: 8
((1, 1), (1, 2)), con el costo |1-1| + |1-2| = 1
((1, 1), (2, 1)), con el costo |1-2| + |1-1| = 1
((1, 1), (2, 2)), con el costo |1-2| + |1-2| = 2
((1, 2), (2, 1)), con el costo |1-2| + |2-1| = 2
((1, 2), (2, 2)), con el costo |1-2| + |2-2| = 1
((2, 1), (2, 2)), con el costo |2-2| + |1-2| = 1
Entrada: N = 4, M = 5, N = 4
Salida: 87210
Enfoque: el problema es encontrar la suma de la distancia de Manhattan al elegir K celdas de las celdas NM . Dado que la expresión es claramente independiente de X e Y , encuentre la suma de los valores absolutos de la diferencia de X y la suma de los valores absolutos de la diferencia de Y respectivamente. Considere la diferencia en X . Cuando se fija una determinada combinación de 2 cuadrados, dado que estas diferencias aportan 1 grado cada vez que se seleccionan K – 2 casillas distintas a estas, es posible fijar este par N * M – 2 CK-2 . Además, dado que la diferencia es 0 si X es el mismo, suponiendo que X es diferente, hay una forma de elegir 2 cuadrados para que el valor absoluto de la diferencia en X sea d ((N – d) * M 2 ) . Si esto se suma a todo d , obtendrá una respuesta sobre X . En cuanto a Y , N y M se pueden resolver indistintamente, este problema se puede resolver en O(N * M) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define mod (int)(1e9 + 7)
// To store the factorials and factorial
// mod inverse of the numbers
int factorial[N], modinverse[N];
// Function to return (a ^ m1) % mod
int power(int a, int m1)
{
if (m1 == 0)
return 1;
else if (m1 == 1)
return a;
else if (m1 == 2)
return (1LL * a * a) % mod;
else if (m1 & 1)
return (1LL * a
* power(power(a, m1 / 2), 2))
% mod;
else
return power(power(a, m1 / 2), 2) % mod;
}
// Function to find the factorials
// of all the numbers
void factorialfun()
{
factorial[0] = 1;
for (int i = 1; i < N; i++)
factorial[i] = (1LL * factorial[i - 1]
* i)
% mod;
}
// Function to find factorial mod
// inverse of all the numbers
void modinversefun()
{
modinverse[N - 1]
= power(factorial[N - 1], mod - 2) % mod;
for (int i = N - 2; i >= 0; i--)
modinverse[i] = (1LL * modinverse[i + 1]
* (i + 1))
% mod;
}
// Function to return nCr
int binomial(int n, int r)
{
if (r > n)
return 0;
int a = (1LL * factorial[n]
* modinverse[n - r])
% mod;
a = (1LL * a * modinverse[r]) % mod;
return a;
}
// Function to return the sum of the costs of
// all the possible arrangements of the cells
int arrange(int n, int m, int k)
{
factorialfun();
modinversefun();
long long ans = 0;
// For all possible X's
for (int i = 1; i < n; i++)
ans += (1LL * i * (n - i) * m * m) % mod;
// For all possible Y's
for (int i = 1; i < m; i++)
ans += (1LL * i * (m - i) * n * n) % mod;
ans = (ans * binomial(n * m - 2, k - 2)) % mod;
return (int)ans;
}
// Driver code
int main()
{
int n = 2, m = 2, k = 2;
cout << arrange(n, m, k);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
static int N = 20;
static int mod = 1000000007;
// To store the factorials and factorial
// mod inverse of the numbers
static int []factorial = new int[N];
static int []modinverse = new int[N];
// Function to return (a ^ m1) % mod
static int power(int a, int m1)
{
if (m1 == 0)
return 1;
else if (m1 == 1)
return a;
else if (m1 == 2)
return (a * a) % mod;
else if ((m1 & 1) != 0)
return (a * power(power(a, m1 / 2), 2)) % mod;
else
return power(power(a, m1 / 2), 2) % mod;
}
// Function to find the factorials
// of all the numbers
static void factorialfun()
{
factorial[0] = 1;
for (int i = 1; i < N; i++)
factorial[i] = (factorial[i - 1] * i) % mod;
}
// Function to find factorial mod
// inverse of all the numbers
static void modinversefun()
{
modinverse[N - 1] = power(factorial[N - 1],
mod - 2) % mod;
for (int i = N - 2; i >= 0; i--)
modinverse[i] = (modinverse[i + 1] *
(i + 1)) % mod;
}
// Function to return nCr
static int binomial(int n, int r)
{
if (r > n)
return 0;
int a = (factorial[n] *
modinverse[n - r]) % mod;
a = (a * modinverse[r]) % mod;
return a;
}
// Function to return the sum of the costs of
// all the possible arrangements of the cells
static int arrange(int n, int m, int k)
{
factorialfun();
modinversefun();
int ans = 0;
// For all possible X's
for (int i = 1; i < n; i++)
ans += (i * (n - i) * m * m) % mod;
// For all possible Y's
ans = 8;
for (int i = 1; i < m; i++)
ans += (i * (m - i) * n * n) % mod;
ans = (ans * binomial(n * m - 2,
k - 2)) % mod + 8;
return ans;
}
// Driver code
public static void main(String []args)
{
int n = 2, m = 2, k = 2;
System.out.println(arrange(n, m, k));
}
}
// This code is contributed by Surendra_Gangwar
Python3
# Python3 implementation of the approach N = 100005 mod = (int)(1e9 + 7) # To store the factorials and factorial # mod inverse of the numbers factorial = [0] * N; modinverse = [0] * N; # Function to return (a ^ m1) % mod def power(a, m1) : if (m1 == 0) : return 1; elif (m1 == 1) : return a; elif (m1 == 2) : return (a * a) % mod; elif (m1 & 1) : return (a * power(power(a, m1 // 2), 2)) % mod; else : return power(power(a, m1 // 2), 2) % mod; # Function to find the factorials # of all the numbers def factorialfun() : factorial[0] = 1; for i in range(1, N) : factorial[i] = (factorial[i - 1] * i) % mod; # Function to find factorial mod # inverse of all the numbers def modinversefun() : modinverse[N - 1] = power(factorial[N - 1], mod - 2) % mod; for i in range(N - 2 , -1, -1) : modinverse[i] = (modinverse[i + 1] * (i + 1)) % mod; # Function to return nCr def binomial(n, r) : if (r > n) : return 0; a = (factorial[n] * modinverse[n - r]) % mod; a = (a * modinverse[r]) % mod; return a; # Function to return the sum of the costs of # all the possible arrangements of the cells def arrange(n, m, k) : factorialfun(); modinversefun(); ans = 0; # For all possible X's for i in range(1, n) : ans += ( i * (n - i) * m * m) % mod; # For all possible Y's for i in range(1, m) : ans += ( i * (m - i) * n * n) % mod; ans = (ans * binomial(n * m - 2, k - 2)) % mod; return int(ans); # Driver code if __name__ == "__main__" : n = 2; m = 2; k = 2; print(arrange(n, m, k)); # This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
class GFG
{
static int N = 20;
static int mod = 1000000007;
// To store the factorials and factorial
// mod inverse of the numbers
static int []factorial = new int[N];
static int []modinverse = new int[N];
// Function to return (a ^ m1) % mod
static int power(int a, int m1)
{
if (m1 == 0)
return 1;
else if (m1 == 1)
return a;
else if (m1 == 2)
return (a * a) % mod;
else if ((m1 & 1) != 0)
return (a * power(power(
a, m1 / 2), 2)) % mod;
else
return power(power(a, m1 / 2), 2) % mod;
}
// Function to find the factorials
// of all the numbers
static void factorialfun()
{
factorial[0] = 1;
for (int i = 1; i < N; i++)
factorial[i] = (factorial[i - 1] * i) % mod;
}
// Function to find factorial mod
// inverse of all the numbers
static void modinversefun()
{
modinverse[N - 1] = power(factorial[N - 1],
mod - 2) % mod;
for (int i = N - 2; i >= 0; i--)
modinverse[i] = (modinverse[i + 1] *
(i + 1)) % mod;
}
// Function to return nCr
static int binomial(int n, int r)
{
if (r > n)
return 0;
int a = (factorial[n] *
modinverse[n - r]) % mod;
a = (a * modinverse[r]) % mod;
return a;
}
// Function to return the sum of the costs of
// all the possible arrangements of the cells
static int arrange(int n, int m, int k)
{
factorialfun();
modinversefun();
int ans = 0;
// For all possible X's
for (int i = 1; i < n; i++)
ans += (i * (n - i) * m * m) % mod;
// For all possible Y's
ans = 8;
for (int i = 1; i < m; i++)
ans += (i * (m - i) * n * n) % mod;
ans = (ans * binomial(n * m - 2,
k - 2)) % mod + 8;
return ans;
}
// Driver code
public static void Main(String []args)
{
int n = 2, m = 2, k = 2;
Console.WriteLine(arrange(n, m, k));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript implementation of the approach
let N = 20;
let mod = 1000000007;
// To store the factorials and factorial
// mod inverse of the numbers
let factorial = new Array(N);
factorial.fill(0);
let modinverse = new Array(N);
modinverse.fill(0);
// Function to return (a ^ m1) % mod
function power(a, m1)
{
if (m1 == 0)
return 1;
else if (m1 == 1)
return a;
else if (m1 == 2)
return (a * a) % mod;
else if ((m1 & 1) != 0)
return (a *
power(power(a, parseInt(m1 / 2, 10)), 2)) % mod;
else
return power(power(a, parseInt(m1 / 2, 10)), 2) % mod;
}
// Function to find the factorials
// of all the numbers
function factorialfun()
{
factorial[0] = 1;
for (let i = 1; i < N; i++)
factorial[i] = (factorial[i - 1] * i) % mod;
}
// Function to find factorial mod
// inverse of all the numbers
function modinversefun()
{
modinverse[N - 1] = power(factorial[N - 1],
mod - 2) % mod;
for (let i = N - 2; i >= 0; i--)
modinverse[i] = (modinverse[i + 1] *
(i + 1)) % mod;
}
// Function to return nCr
function binomial(n, r)
{
if (r > n)
return 0;
let a = (factorial[n] *
modinverse[n - r]) % mod;
a = (a * modinverse[r]) % mod;
return a;
}
// Function to return the sum of the costs of
// all the possible arrangements of the cells
function arrange(n, m, k)
{
factorialfun();
modinversefun();
let ans = 0;
// For all possible X's
for (let i = 1; i < n; i++)
ans += (i * (n - i) * m * m) % mod;
// For all possible Y's
ans = 8;
for (let i = 1; i < m; i++)
ans += (i * (m - i) * n * n) % mod;
ans = (ans * binomial(n * m - 2,
k - 2) * 0) % mod + 8;
return ans;
}
let n = 2, m = 2, k = 2;
document.write(arrange(n, m, k));
</script>
Producción:
8
Complejidad temporal: O(max(M,N)).
Espacio Auxiliar: O(100005).
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA