Блог

Ну, мы все знаем, что при наличии n узлов и m ребер мы можем найти количество возможных способов перехода от 1 к n, используя какой-либо алгоритм, подобный dfs. Но рассмотрим случай, когда мы должны исходить из обратной стороны. Я имею в виду, что нам не дано ни одного из способов, т. е. x, достичь n из 1 в вопросе. И мы должны выяснить, что n узлов и что m ребер, по которым, если мы построим этот график на бумаге, у него будет ровно x способов достижения от 1 до n.

Ограничения также существуют для n и m. n<= 300 и m <= 400. и, что удивительно, ограничения ни для одного из способов ‘x’ не равны 10 ^ 18.

Возможно ли сформировать график при таких ограничениях?

Обратите внимание, что граф должен быть ориентированным ациклическим графом без самостоятельного цикла.

Допустим, W, количество путей, равно степени 2, то есть 2 ^ x . Давайте попробуем построить график с W путями от 1 до n.

График может выглядеть следующим образом:

 1 -> 2,
1 -> 3,
2 -> 4,
3 -> 4
4 -> 5,     
4 -> 6,
5 -> 7,
6 -> 7,
...
  

Как вы можете видеть, вы можете создавать небольшие «ромбы», каждый из которых умножает количество путей на 2. Если число равно 2^ 62, вам понадобится 1 3 * 62 = 187 узлов и 4 * 62 = 248 ребер.

Теперь предположим, что W = 2 ^ x 2 ^ y, x < y. Создайте график ромбов для W’ = 2 ^ y . Чтобы добавить 2 ^ x путей, соедините начальную вершину с am ребром с вершиной, которая находится на расстоянии x ромбов от конечной. Вы можете легко вычислить, что количество путей действительно будет равно 2 ^ x 2 ^ y.

Итак, для произвольного W перепишите его как сумму различных степеней 2, создайте график ромбов для наибольшей степени и добавьте дополнительные ребра, чтобы добавить остальные степени. Вам потребуется до 187 узлов (добавление ребер к графику ромбов не влияет на количество узлов) и 248 ребер для наибольшей степени 61 для остальных степеней. Он удовлетворяет вашим ограничениям.