11455. K специальных ячеек

Вам дана матрица размером n × m, в которой выделены k специальных ячеек. Необходимо добраться из клетки (1, 1) в клетку (n, m). Разрешается двигаться только вправо или вниз.

Каждая из k специальных ячеек обладает определённой силой. i-я специальная ячейка имеет силу p_i, и при прохождении через неё вы получаете эту силу.

Требуется найти суммарную силу, которую можно набрать, рассматривая все возможные пути от (1, 1) до (n, m).

Заметим, что:

· Сила пути определяется как сумма значений p_i всех специальных ячеек, посещённых на этом пути.

· Обычные ячейки, не являющиеся специальными, имеют силу, равную нулю.

Вход. Первая строка содержит целое число t – количество тестов.

В первой строке каждого теста заданы три целых числа n, m (1 ≤ n, m ≤ 10⁵) и k (1 ≤ k ≤ 10⁶), где n ∗ m – размер сетки, а k – количество специальных ячеек.

Каждая из следующих k строк содержит три числа x_i, y_i (1 ≤ x_i ≤ n, 1 ≤ y_i ≤ m) и p_i (1 ≤ p_i ≤ 10⁵), где (x_i, y_i) – координаты специальной ячейки, а p_i – её сила.

Выход. Для каждого теста выведите в отдельной строке суммарную силу, которую можно набрать. Так как ответ может быть очень большим, выведите его по модулю 10⁹ + 7.

Пример входа	Пример выхода
1 2 2 2 1 2 4 2 1 7	11

РЕШЕНИЕ

комбинаторика

Анализ алгоритма

Пусть ways(x, y) обозначает количество путей на матрице из клетки (1, 1) в клетку (1 + x, 1 + y). Тогда

ways(x, y) = =

Количество путей из клетки (1, 1) в клетку (n, m), проходящих через специальную ячейку (x, y), равно ways(x – 1, y – 1) * ways(n – x, m – y). Умножив это число на p, получаем суммарную силу всех путей, проходящих через ячейку (x, y).

Остается просуммировать силы всех путей, проходящих через специальные ячейки. Ответ будет равен сумме:

Пример

В приведенном примере заданы k = 2 специальные ячейки.

· Ровно один путь проходит через ячейку с силой 4.

· Ровно один путь проходит через ячейку с силой 7.

Таким образом, общая сила равна 4 + 7 = 11.

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

Объявим массивы:

· fact содержит факториалы чисел по модулю MOD,

· factinv содержит обратные значения к этим факториалам по модулю MOD:

fact[n] = n! mod 1000000007

factinv[n] = n! ^-1 mod 1000000007

#define MAX 800001

ll fact[MAX], factinv[MAX];

Функция pow вычисляет степень числа по модулю: xⁿ 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 mod p = 1 для любого 1 ≤ x < p

Его можно переписать в виде (x * x^p-2) mod p = 1, откуда следует, что обратным к x является число x^p-2 mod p.

ll inverse(ll x, ll p)

{

return pow(x, p - 2, p);

}

Функция Cnk вычисляет биномиальный коэффициент по формуле:

=

ll Cnk(int n, int k)

{

return ((fact[n] * factinv[k]) % MOD * factinv[n - k]) % MOD;

}

Функция ways вычисляет количество путей на решетке размером n × m из клетки (0, 0) в клетку (n, m). Так как любой путь между этими точками имеет длину n + m и содержит ровно m горизонтальных сегментов, число путей равно .

ll ways(int n, int m)

{

return Cnk(n + m, m);

}

Основная часть программы. Заполняем массивы факториалов fact и обратных факториалов 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);

Последовательно обрабатываем tests тестов.

scanf("%d", &tests);

while (tests--)

{

Читаем данные текущего теста.

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

Суммарную полученную силу сохраняем в переменной res.

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

}