Как найти количество помеченных связных графов?
Задача похожа на codeforces 1009D, но только с одним числом в вводе Можете пожалуйста написать способ нахождения помеченных связных графов когда на вход подается только одно число?(если не затрудняет то с кодом)
Ответы (1 шт):
Автор решения: MBo
→ Ссылка
Степень n-1 должна быть у одной вершины. Отделим её и поищем решение задачи для количества графов, у которых ни одна из вершин не имеет максимальной степени.
А тема такая, оказывается, есть. Посчитаем это количество для n-1 вершин и умножим на n
result = n * numconn(n-1)
Получим 3, 16, 205, 4608... Остаётся перевести на арифметику по модулю 1000000007 (-1 в степени при этом лучше будет по-простому сделать - то плюс, то минус)