Given two integers N and M. At each operation, choose K cells of a 2D grid of size N * M and arrange them. If we choose the K cells (x1, y1), (x2, y2), …, and (xK, yK) then the cost of this arrangement is computed as ?i=1K-1 ?j=i+1K (|xi – xj| + |yi – yj|). The task is to find the sum of the costs of all possible arrangements of the cells. The answer can be very large so print the answer modulo 109 + 7
Examples:
Input: N = 2, M = 2, K = 2
Output: 8
((1, 1), (1, 2)), with the cost |1-1| + |1-2| = 1
((1, 1), (2, 1)), with the cost |1-2| + |1-1| = 1
((1, 1), (2, 2)), with the cost |1-2| + |1-2| = 2
((1, 2), (2, 1)), with the cost |1-2| + |2-1| = 2
((1, 2), (2, 2)), with the cost |1-2| + |2-2| = 1
((2, 1), (2, 2)), with the cost |2-2| + |1-2| = 1
Input: N = 4, M = 5, N = 4
Output: 87210
Approach: Problem is to find the sum of the Manhattan distance when choosing K cells out of the N-M cells. Since the expression is clearly independent of X and Y, find the sum of the absolute values of the difference of X and the sum of the absolute values of the difference of Y respectively. Consider the difference in X. When a certain combination of 2 squares is fixed, since these differences contribute 1 degree each time when selecting K – 2 cells from other than these, it is possible to fix this pair N * M – 2CK – 2. Furthermore, since the difference is 0 if X is the same, assuming X is different, there is a way to choose 2 squares so that the absolute value of the difference in X is d ((N – d) * M2). If this is added to all d, you will get an answer about X. As for Y, N and M can be solved interchangeably, this problem can be solved in O(N * M).
Below is the implementation of the above approach:
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 numbersint factorial[N], modinverse[N];// Function to return (a ^ m1) % modint 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 numbersvoid 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 numbersvoid 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 nCrint 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 cellsint 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 codeint main(){ int n = 2, m = 2, k = 2; cout << arrange(n, m, k); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{static int N = 20;static int mod = 1000000007;// To store the factorials and factorial// mod inverse of the numbersstatic int []factorial = new int[N];static int []modinverse = new int[N];// Function to return (a ^ m1) % modstatic 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 numbersstatic 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 numbersstatic 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 nCrstatic 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 cellsstatic 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 codepublic 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 = 100005mod = (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 approachusing System;class GFG{static int N = 20;static int mod = 1000000007;// To store the factorials and factorial// mod inverse of the numbersstatic int []factorial = new int[N];static int []modinverse = new int[N];// Function to return (a ^ m1) % modstatic 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 numbersstatic 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 numbersstatic 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 nCrstatic 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 cellsstatic 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 codepublic 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> |
Output:
8
Time Complexity: O(max(M,N)).
Auxiliary Space: O(100005).
