k спеціальних клітин#11455

k спеціальних клітин (Розбір)

Нехай $w a y s (x, y)$ ways(x, y) позначає кількість шляхів на матриці з клітинки $(1, 1)$ до клітинки $(1 + x, 1 + y)$ (1 + x, 1 + y). Тоді

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

Кількість шляхів з клітинки $(1, 1)$ до клітинки $(n, m)$ , що проходять через спеціальну комірку $(x, y)$ , дорівнює $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). Помноживши це число на $p$ , отримаємо сумарну силу всіх шляхів, які проходять через комірку $(x, y)$ .

Залишається просумувати сили всіх шляхів, що проходять через спеціальні комірки. Відповідь буде рівна сумі:

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

Приклад

У наведеному прикладі задані $k = 2$ k = 2 спеціальні комірки.

Рівно один шлях проходить через комірку з силою $4$ .
Рівно один шлях проходить через комірку з силою $7$ .

Таким чином, загальна сила дорівнює $4 + 7 = 11$ 4 + 7 = 11.

Реалізація алгоритму

Оголосимо масиви:

$f a c t$ містить факторіали чисел за модулем $M O D$ ,
$f a c t in v$ factinv містить обернені значення до цих факторіалів за модулем $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];

Функція pow обчислює степінь числа за модулем: $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;
}

Функція inverse знаходить число, обернене до $x$ за простим модулем $p$ . Оскільки $p$ — просте число, то згідно з малою теоремою Ферма виконується рівність:

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

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

Його можна переписати у вигляді $(x \cdot x^{p - 2}) m o d p = 1$ (x \cdot x^{p-2})~mod~p = 1, звідки слідує, що оберненим до $x$ є число $x^{p - 2} m o d p$ x^{p-2}~mod~p.

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

Функція Cnk обчислює біноміальний коефіцієнт за формулою:

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;
}

Функція ways обчислює кількість шляхів на ґратці розміром $n \times m$ n \times m з клітинки $(0, 0)$ до клітинки $(n, m)$ . Оскільки будь-який шлях між цими точками має довжину $n + m$ n + m і містить рівно $m$ горизонтальних сегментів, кількість шляхів дорівнює $C_{n + m}^{m}$ C_{n+m}^m.

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

Основна частина програми. Заповнюємо масиви факторіалів $f a c t$ і обернених факторіалів $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++

Послідовно обробляємо $t es t s$ тестів.

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

Зчитуємо дані поточного тесту.

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

Сумарну отриману силу зберігаємо в змінній $r es$ .

  res = 0;

Обробляємо $k$ спеціальних комірок.

  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;
  }

Виводимо відповідь для поточного тесту.

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