[C++/Python] Combinatorics - 0ms O(1) - Complete Proof
DerivationMy explanation relies on n representing number of rows and m representing number of columns.
Fix the two cells we will be calculating the distances on
![image.png](https://assets.leetcode.com/users/images/ea57a904-3365-4417-a5ac-c3914afd16cc_1737222655.565341.png)

# Derivation
My explanation relies on $n$ representing number of rows and $m$ representing number of columns.
- Fix the two cells we will be calculating the distances on. Let their manhattan distance be $dist$. The number of valid arrangements of pieces WHILE those two pieces are fixed ($k - 2$ left) is ${n*m - 2} \choose {k - 2}$. PieceContribution = $dist * CountOfValidArrangement$ = $dist * \binom{n*m - 2}{k - 2}$
- You can easily calculate this in $O(n * m)$ which does pass by looping through all cells and calculating the distance to all other cells multiplied by $CountOfValidArrangements$. 
- Because that right part is a **constant**, we can optimize this into $O(n + m)$ complexity. Divide the problem into calculating the total of row distances and total of column distances.
- Say we are calculating the row distances. For each row $r$:
    * There are $m$ cells in this row. We don't need to calculate the distance between cells of the same row because $dist = 0$. We don't need to calculate with row less than $r$ otherwise we would double-count the contributions. (Although this is also okay if you divide by 2 at the end)
    * The other rows each also have $m$ cells. There are $m$ cells with distance $y$ if there are any. The number of pairing between any cell in this row and any other row is equal to $m *m=m^2$ ($m$ cells in this row, $m$ cells in other row), so $totalDist=m^2*dist$ where $r+dist$ is a valid row.
    * $r+dist<n$
      $dist<n-r$
      $dist \le n-r-1$
    * Let $contribution$ be $\binom{n*m - 2}{k - 2}$ (from earlier). Calculate:
      $$contribution*m^2*dist \newline
      contribution*m^2 * (1 +2+...+(n - r - 1)) \newline
      contribution*m^2 * Sum(1, n - r - 1) \newline
      contribution*m^2 * \frac{cnt*(A_0+A_{cnt})}{2} \newline
      contribution*m^2 * \frac{(n - r - 1)*(n-r)}{2} \newline
      contribution*m^2*(n-r-1)*(n-r)/2
$$
- Do the same thing but with column distances for column $c$:
 $ contribution*n^2*(m-c-1)*(m-c)/2$
- $O(1)$ solution is possible.
  * Sum of across all $r=0 \rightarrow n, (n-r)*(n-r-1)$ simplifies to $\frac{(n-1)*n*(n+1)}{3}$
  * $$\sum_{r=0}^{n}(n-r) \cdot (n-r-1) \newline
    = \sum_{r=0}^{n}(n^2-nr-n-nr+r^2+r) \newline
    = \sum_{r=0}^{n}(n^2-n-2nr+r^2+r) \newline
    = \sum_{r=0}^{n}n^2-\sum_{r=0}^{n}n-\sum_{r=0}^{n}2nr+\sum_{r=0}^{n}r^2+\sum_{r=0}^{n}r \newline
    = (n+1)n^2-(n+1)n-2n\cdot\sum_{r=0}^{n}r+\sum_{r=0}^{n}r^2+\sum_{r=0}^{n}r \newline
    = (n+1)n^2-(n+1)n-(2n - 1)\cdot\sum_{r=0}^{n}r+\sum_{r=0}^{n}r^2 \newline
    = (n+1)n^2-(n+1)n+\sum_{r=0}^{n}r^2-(2n - 1)\cdot\sum_{r=0}^{n}r \newline
    = (n+1)n^2-(n+1)n+(0^2+1^2+2^2+...+n^2)-(2n - 1)\cdot\sum_{r=0}^{n}r \newline
    = (n+1)n^2-(n+1)n+\frac{n(n+1)(2n+1)}{6}-(2n - 1)\cdot\sum_{r=0}^{n}r \newline
    = (n+1)n^2-(n+1)n+\frac{n(n+1)(2n+1)}{6}-(2n - 1)\cdot(0+1+2+...+n) 
\newline
    = (n+1)n^2-(n+1)n+\frac{n(n+1)(2n+1)}{6}-(2n - 1)\frac{n(n+1)}{2} \newline
    = (n+1)n^2-(n+1)n+\frac{n(n+1)(2n+1)}{6}-\frac{n(n+1)(2n-1)}{2} \newline
    = \frac{6(n+1)n^2}{6}-\frac{6(n+1)n}{6}+\frac{n(n+1)(2n+1)}{6}-\frac{3n(n+1)(2n-1)}{6} \newline
    = \frac{6(n+1)n^2-6(n+1)n+n(n+1)(2n+1)-3n(n+1)(2n-1)}{6} \newline
    = \frac{(n+1)6n^2-(n+1)6n+(n+1)n(2n+1)-(n+1)3n(2n-1)}{6} \newline
    = \frac{(n+1)(6n^2-6n+n(2n+1)-3n(2n-1))}{6} \newline
    = \frac{(n+1)(n*6n-n*6+n(2n+1)-n*3(2n-1))}{6} \newline
    = \frac{(n+1)n(6n-6+(2n+1)-3(2n-1))}{6} \newline
    = \frac{(n+1)n(6n-6+2n+1-6n+3)}{6} \newline
    = \frac{(n+1)n(6n-6n+2n-6+1+3)}{6} \newline
    = \frac{(n+1)n(2n-6+1+3)}{6} \newline
    = \frac{(n+1)n(2n-2)}{6} \newline
    = \frac{(n+1)n(2*(n-1))}{6} \newline
    = \frac{(n+1)n((n-1))}{3} \newline
    = \frac{(n+1)n(n-1)}{3} \newline
    = \frac{(n-1)\cdot n\cdot(n+1)}{3} \newline
    = \frac{1}{3}(n-1)\cdot n\cdot(n+1) \newline
$$
  * We have proven that $\sum_{r=0}^{n}(n-r) \cdot (n-r-1) = \frac{1}{3}(n-1)\cdot n\cdot(n+1)$. Now, we substitute.
  * $$
\sum_{r=0}^{n}(contribution \cdot m^2 \cdot (n-r-1) \cdot (n-r) \cdot \frac{1}{2}) \newline
= \frac{1}{2} \cdot contribution \cdot m^2 \cdot \sum_{r=0}^{n}((n-r-1) \cdot (n-r)) \newline
= \frac{1}{2} \cdot contribution \cdot m^2 \cdot \frac{1}{3}(n-1)(n)(n+1) \newline
= \frac{1}{6} \cdot contribution \cdot m^2 \cdot (n-1)(n)(n+1)$$
  * Due to the symmetry of row and column distances, you can flip all $m$ and $n$ for the other contribution: $$\frac{1}{6} \cdot contribution \cdot n^2 \cdot (m-1)(m)(m+1)$$
  * $$
\frac{1}{6} \cdot contribution \cdot m^2 \cdot (n-1)(n)(n+1) + \frac{1}{6} \cdot contribution \cdot n^2 \cdot (m-1)(m)(m+1) \mod 1000000007 \newline
=  \frac{1}{6}\binom{n*m - 2}{k - 2}(m^2(n-1)n(n+1)+n^2(m-1)m(m+1)) \mod 1000000007
$$
  * The final formula which can be easily calculated in O(1) with precomputation is: $\frac{1}{6}\binom{n*m - 2}{k - 2}(m^2(n-1)n(n+1)+n^2(m-1)m(m+1)) \mod 1000000007$
- Weird that they allow as worse as $O(n*m)$ even though $O(1)$ is possible and fit more as Q4.
# Complexity
- Time complexity: $O(1)$ **with precomputation**

- Space complexity: $O(1)$

# Code O(1)
### Note: true O(1) is ONLY achieved when N choose K is precomputed. 
### Below this code are other versions: O(1) C++, O(n+m) Python/C++, O(n*m) Python.

---
# True O(1) in Python, next: True O(1) in C++
```python3 []
MOD = 10**9 + 7
factorial = [1, 1]
invfactorial = [1, 1]

def nCk(n, k):
    return factorial[n] * invfactorial[k] % MOD * invfactorial[n-k] % MOD

class Solution:
    def distanceSum(self, m: int, n: int, k: int) -> int:
        return (nCk(n*m - 2, k - 2) * (m * m * (n - 1) * n * (n + 1) + n * n * (m - 1) * m * (m + 1)) // 6) % MOD

def mod_inv(base):
    ans = 1
    exp = MOD - 2
    while exp > 0:
        if exp % 2 == 1:
            ans = (ans * base) % MOD
        exp //= 2
        base = (base * base) % MOD
    return ans

for i in range(2, 100_000):
    factorial.append(i * factorial[i - 1] % MOD)
    invfactorial.append(mod_inv(factorial[i]) % MOD)
```
---
# True O(1) in C++, next: O(n+m) Python
```cpp []
#include <bits/stdc++.h>
using namespace std;
long long mod_exp(long long base, int exp, long long mod) {
    long long ans = 1;
    base %= mod;
    while(exp > 0) {
        if(exp & 1) ans = (ans * base) % mod;
        exp >>= 1;
        base = (base * base) % mod;
    }
    return ans;
}
const long long FMOD = 1e9 + 7;
vector<long long> factorial {1,1}, invfactorial {1,1};

long long calcFactorial(long long n) {
    for(long long i = factorial.size(); i <= n; i++) {
        factorial.push_back(i * factorial[i - 1]);
    }
    return factorial[n];
}
long long modfactorial(long long n) {
    for(long long i = factorial.size(); i <= n; i++) {
        factorial.push_back((i * factorial[i - 1]) % FMOD);
        invfactorial.push_back((mod_exp(i, FMOD-2, FMOD) * invfactorial[i - 1]) % FMOD);
    }
    return factorial[n];
}
const long long MAXFACTORIALN = 100'001;
auto precomputeModFactorial = []() { modfactorial(MAXFACTORIALN); return true; }();
long long nCkMod(int N, int K) {
    return factorial[N] * invfactorial[K] % FMOD * invfactorial[N-K] % FMOD;
}
const long long MOD = 1e9 + 7;
const long long DIVIDE_BY_6 = mod_exp(6, MOD-2, MOD);
class Solution {
public:
    int distanceSum(int n, int m, int k) {
        return nCkMod(n*m-2, k-2) * (
            (1LL * m * m % MOD * (n - 1) % MOD * (n) % MOD * (n + 1) % MOD * DIVIDE_BY_6 % MOD) + 
            (1LL * n * n % MOD * (m - 1) % MOD * (m) % MOD * (m + 1) % MOD * DIVIDE_BY_6 % MOD)) % MOD;
    }
};
```
---
# O(n+m) Python, next: O(n+m) C++
```python3 []
MOD = 10**9 + 7
DIV_2 = (MOD + 1) // 2
factorial = [1, 1]
invfactorial = [1, 1]

def nCk(n, k):
    return factorial[n] * invfactorial[k] % MOD * invfactorial[n-k] % MOD

def mod_inv(base):
    ans = 1
    exp = MOD - 2
    while exp > 0:
        if exp % 2 == 1:
            ans = (ans * base) % MOD
        exp //= 2
        base = (base * base) % MOD
    return ans

class Solution:
    def distanceSum(self, m: int, n: int, k: int) -> int:
        ans, contribution = 0, nCk(n*m - 2, k - 2)
        for r in range(n - 1):
            ans = (ans + contribution * m % MOD * m % MOD * (n - r - 1) % MOD * (n - r) % MOD * DIV_2) % MOD
        for c in range(m - 1):
            ans = (ans + contribution * n % MOD * n % MOD * (m - c - 1) % MOD * (m - c) % MOD * DIV_2) % MOD
        return ans

for i in range(2, 100_000):
    factorial.append(i * factorial[i - 1] % MOD)
    invfactorial.append(mod_inv(factorial[i]) % MOD)
```
---
# O(n+m) C++, next: O(n*m) Python
```cpp []
#include <bits/stdc++.h>
using namespace std;
long long mod_exp(long long base, int exp, long long mod) {
    long long ans = 1;
    base %= mod;
    while(exp > 0) {
        if(exp & 1) ans = (ans * base) % mod;
        exp >>= 1;
        base = (base * base) % mod;
    }
    return ans;
}
const long long FMOD = 1e9 + 7;
vector<long long> factorial {1,1}, invfactorial {1,1};

long long calcFactorial(long long n) {
    for(long long i = factorial.size(); i <= n; i++) {
        factorial.push_back(i * factorial[i - 1]);
    }
    return factorial[n];
}
long long modfactorial(long long n) {
    for(long long i = factorial.size(); i <= n; i++) {
        factorial.push_back((i * factorial[i - 1]) % FMOD);
        invfactorial.push_back((mod_exp(i, FMOD-2, FMOD) * invfactorial[i - 1]) % FMOD);
    }
    return factorial[n];
}
const long long MAXFACTORIALN = 100'001;
auto precomputeModFactorial = []() { modfactorial(MAXFACTORIALN); return true; }();
long long nCkMod(int N, int K) {
    return factorial[N] * invfactorial[K] % FMOD * invfactorial[N-K] % FMOD;
}
const long long MOD = 1e9 + 7;

class Solution {
public:
    int distanceSum(int n, int m, int k) {
        long long ans = 0, contribution = nCkMod(n*m-2, k-2);
        for(int r = 0; r < (n - 1); r++) {
            ans += contribution * m % MOD * m * (n - r - 1) % MOD * (n - r) % MOD * mod_exp(2, MOD-2, MOD);
            ans %= MOD;
        }
        for(int c = 0; c < (m - 1); c++) {
            ans += contribution * n % MOD * n * (m - c - 1) % MOD * (m - c) % MOD * mod_exp(2, MOD-2, MOD);
            ans %= MOD;
        }
        return ans;
    }
};
```
---
# O(n*m) Python
```python3 []
class Solution:
    def distanceSum(self, m: int, n: int, k: int) -> int:
        ans = 0
        contribution = comb(n*m - 2, k - 2)
        for r in range(n - 1):
            ans += contribution * m * m * (n - r - 1) * (n - r) // 2
        for c in range(m - 1):
            ans += contribution * n * n * (m - c - 1) * (m - c) // 2
        return ans % (10**9 + 7)
```

['Combinatorics', 'Python', 'C++']