Я практикуюсь в ACM ICPC, и я столкнулся с этой проблемой с 2017 ACM ICPC Arab Regionals:
Во-первых, давайте определим ненаправленный связанный помеченный граф, это граф с N узлами с уникальной меткой
для каждого узла и некоторых ребер нет конкретного направления для каждого ребра, также дублируются ребра и ребра
от узла к себе не допускается, и с любого узла вы можете связаться с любым другим узлом.
Мост в таком графе - это ребро, которое, если мы его удалим, будет отключено
существуют узлы, которые не достижимы друг от друга).
В этой задаче вам даны N и K, а ваша задача - подсчитать количество разных ненаправленных
связные помеченные графы с ровно N узлами и K мостами. Поскольку это число может быть огромным, напечатайте
это по модулю М.
Ребро определяется с помощью меток узлов, которые он соединяет, например, мы можем сказать (X, Y) является
ребро между X и Y также (Y, X) считается тем же ребром (так как оно не направлено). Два графика
считаться другим, если в одном из них есть ребро, а в другом нет.
Введите:
Ваша программа будет протестирована на одном или нескольких тестовых случаях. Первая строка ввода будет одним целым числом
T (1 ≤ T ≤ 100), представляющее количество тестовых случаев. Затем следуют тесты T.
Каждый тестовый пример будет представлять собой одну строку, содержащую 3 целых числа, разделенных пробелом, N (1 ≤ N ≤ 50), K
(0 ≤ K
Выход:
Для каждого теста выведите в отдельной строке количество графиков, как описано выше по модулю M.
Sample Input:
4
3 2 10
3 0 10
6 3 10000
6 3 1000
Sample Output
3
1
2160
160
Я пытался придумать какую-то формулу, которая работала бы для всех N и K, но у меня не было успеха. Может кто-нибудь сказать мне, что я должен сделать, чтобы решить это, потому что я не мог найти какую-либо редакционную статью? Заранее спасибо