| Автор: | Vasilii Parnikov | Ограничение времени: | 1 сек | |
| Входной файл: | Стандартный вход | Ограничение памяти: | 256 Мб | |
| Выходной файл: | Стандартный выход |
Дано полное k-арное дерево глубины h. k-арным называется корневое дерево где у каждой вершины не более k детей. Полным k-арным деревом глубины h называется k-арное дерево у которого все листы находятся на глубине h и у всех вершин k или 0 детей. Глубиной вершины в корневом дереве называется количество рёбер в простом пути от вершины до корня дерева.
Треугольником назовём неупорядоченную тройку различных вершин таких, что ровно одна вершина из тройки является предком двух остальных. Вершина u называется предком вершины v, если u лежит в простом пути от v до корня дерева.
Пусть edge — некоторое ребро в дереве. Обозначим f(edge) = количеству треугольников в двух деревьях которые получатся при удалении ребра edge в исходном дереве.
Авторы задачи ещё не решили, какое именно ребро является лишним. Пока они спорят, вычислите ∑edge − ребро дерева f(edge), то есть сумму количества треугольников в двух деревьях по всем деревьям равным исходному с одним удалённым ребром.
Так как ответ может быть слишком большим, выведите его по модулю 998244353.
Единственная строка входных данных содержит два целых числа k и h.
Выведите одно число — ответ на задачу по модулю 998244353.
2 ≤ k < 998244353, 2 ≤ h ≤ 103
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|
Найдем сперва количество треугольников в дереве без удаленных ребер. Назовем верхней вершиной трегольника ту, вершину которая является предком двух остальных вершин треугольника. Рассмотрим вершину u, и посчитаем для него количество треугольников в которых он является верхней вершиной. Так как он должен быть предком двух остальных вершин в треугольнике, количество таких треугольников равно C2s(u), где s(u) — количество потомков вершины u минус 1, так как u является для самого себя потомком но в треугольнике все вершины различны. То есть s(u) равен размеру его поддерева минус 1. s(u) легко можно найти с помощью формулы суммы геометрической прогрессии. Понятно, что сумма C2s(u) по всем вершинам дерева это количество всех треугольников в дереве. Чтобы сделать это за O(h) можно заметить, что у вершин на одинаковой глубине одинаковое значение s(u), следовательно одинаковое значение C2s(u). Тогда можно перебрать все глубины от 0 до h и умножив C2s(u) на количество вершин на рассматриваемой глубине получим количество треугольников, чья верхняя вершина лежит на такой глубине.
Теперь посмотрим как изменится количество треугольников при удалении ребра. Обозначим v вершину на нижнем конце ребра. Некоторые треугольники исчезнут, так как из-за удаления ребра некоторые вершины перестанут быть предками вершин в поддереве v. Найдем количество треугольников которые исчезнут при удалении ребра. Очевидно, что исчезнут только деревья у которых верхняя вершина будет предком v. Поэтому пройдемся по всем предкам p вершины v, их не более O(h). Количество исчезнувших (при удалении ребра) треугольников с верхней вершиной p равно количеству треугольников с верхней вершиной p и двумя остальными вершинами в поддереве v плюс количество треугольников с верхней вершиной p, со второй вершиной в поддереве v и с третьей в поддереве p но не в поддереве v. Все значения чисел опять зависят только от глубины v. Поэтому вместо перебора всех v можно перебрать только глубины которые может иметь v. Тогда внешним циклом перебираем O(h) глубин, и внутренним циклом O(h) предков v. Итоговая сложность решения O(h2).