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