Дороги после землетрясения


Отправить решение Решать в редакторе

Сложность: 90%
Очки: 100 (частичный балл)
Ограничение по времени: 3.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

В горах Джалал-Абадской области n сёл соединены m дорогами (между двумя сёлами может быть несколько дорог). После землетрясения дорога i осталась проезжей с вероятностью p[i] / 100, независимо от других дорог.

Спасатели хотят знать, с какой вероятностью из любого села всё ещё можно добраться до любого другого по проезжим дорогам.

Рисунок

Ответ — рациональное число P / Q; выведите P · Q⁻¹ по модулю 998244353.

Входные данные

В первой строке — два целых числа n и m (1 ≤ n ≤ 16, 0 ≤ m ≤ 200). В каждой из следующих m строк — три целых числа u v p (1 ≤ u, v ≤ n, u ≠ v, 0 ≤ p ≤ 100).

Выходные данные

Выведите вероятность того, что все сёла связаны, по модулю 998244353.

Пример 1

Вход:

3 3
1 2 50
2 3 50
1 3 50

Выход:

499122177

Пояснение

Треугольник из дорог с вероятностями 1/2: сёла связаны, если уцелели хотя бы две дороги из трёх, — это 4 случая из 8, вероятность 1/2 (по модулю 499122177).

Система оценивания

Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов m ≤ 12, ещё в 10 % тестов n ≤ 10.


Комментарии

Еще нет ни одного комментария.