K special cells (Editorial)

K special cells#11455

Let $w a y s (x, y)$ ways(x, y) denote the number of paths on a grid from cell $(1, 1)$ to cell $(1 + x, 1 + y)$ (1 + x, 1 + y). Then

w a y s (x, y) = C_{x + y}^{x} = C_{x + y}^{y}

ways(x, y) = C_{x + y}^x = C_{x + y}^y

The number of paths from cell $(1, 1)$ to cell $(n, m)$ that pass through a special cell $(x, y)$ is equal to $w a y s (x - 1, y - 1) \cdot w a y s (n - x, m - y)$ ways(x - 1, y - 1) \cdot ways(n - x, m - y). Multiplying this number by $p$ gives the total power of all paths passing through cell $(x, y)$ .

It remains to sum the powers of all paths passing through the special cells. The answer will be equal to the sum:

i = 1 \sum k w a y s (x_{i} - 1, y_{i} - 1) \cdot w a y s (n - x_{i}, m - y_{i}) \cdot p_{i}

\sum_{i = 1}^k ways(x_i - 1, y_i - 1) \cdot ways(n - x_i, m - y_i) \cdot p_i

Example

In the given example, $k = 2$ k = 2 special cells are specified.

Exactly one path passes through the cell with power $4$ .
Exactly one path passes through the cell with power $7$ .

Thus, the total power is $4 + 7 = 11$ 4 + 7 = 11.

Algorithm implementation

Declare the arrays:

$f a c t$ contains the factorials of numbers modulo $M O D$ ,
$f a c t in v$ factinv contains the inverse values of these factorials modulo $M O D$ :

f a c t [n] = n! m o d 1000000007 f a c t in v [n] = n!^{- 1} m o d 1000000007

fact[n] = n!~mod~1000000007 \\ factinv[n] = n!^{-1}~mod~1000000007

#define MAX 800001
ll fact[MAX], factinv[MAX];

The pow function computes the power of a number modulo $p$ : $x^{n} m o d p$ x^n~mod~p.

ll pow(ll x, ll n, ll p)
{
    if (n == 0) return 1;
    if (n % 2 == 0) return pow((x * x) % p, n / 2, p);
    return (x * pow(x, n - 1, p)) % p;
}

The inverse function finds the number that is the modular inverse of $x$ with respect to a prime modulo $p$ . Since $p$ is a prime number, by Fermat's Little Theorem the following holds:

x^{p - 1} m o d p = 1 для любого 1 \leq x < p

x^{p-1}~mod~p~=~1~для~любого~1~\le~x~<~p

This can be rewritten as $(x \cdot x^{p - 2}) m o d p = 1$ (x \cdot x^{p-2})~mod~p = 1, from which it follows that the modular inverse of $x$ is $x^{p - 2} m o d p$ x^{p-2}~mod~p.

ll inverse(ll x, ll p)
{
  return pow(x, p - 2, p);
}

The Cnk function computes the binomial coefficient using the formula:

C_{n}^{k} = \frac{n !}{k ! ( n - k )!}

C_n^k = {n! \over k! (n - k)!}

ll Cnk(int n, int k)
{
  return ((fact[n] * factinv[k]) % MOD * factinv[n - k]) % MOD;
}

The ways function calculates the number of paths on an $n \times m$ n \times m grid from cell $(0, 0)$ to cell $(n, m)$ . Since any path between these points has length $n + m$ n + m and contains exactly $m$ horizontal steps, the number of paths is equal to $C_{n + m}^{m}$ C_{n+m}^m.

ll ways(int n, int m)
{
  return Cnk(n + m, m);
}

The main part of the program. Fill the arrays of factorials $f a c t$ and inverse factorials $f a c t in v$ factinv.

fact[0] = 1;
for (i = 1; i < MAX; i++)
  fact[i] = (fact[i - 1] * i) % MOD;

factinv[0] = 1;
for (i = 1; i < MAX; i++)
  factinv[i] = inverse(fact[i], MOD);

C++

Process the tests sequentially.

scanf("%d", &tests);
while (tests--)
{

Read the data for the current test.

  scanf("%d %d %d", &n, &m, &k);

Store the total obtained power in the variable $r es$ .

  res = 0;

Process the $k$ special cells.

  for (i = 0; i < k; i++)
  {
    scanf("%d %d %d", &x, &y, &p);
    res = (res + (ways(x - 1, y - 1) * 
                  ways(n - x, m - y)) % MOD * p) % MOD;
  }

Print the answer for the current test.

  printf("%lld\n", res);
}