Задача: написать функцию, которая принимает на вход целое число точек и возвращает количество способов соединить эти точки. Отсутствие соединения между точками тоже считается за способ. Для 8 точек - ответ 64, для 2 точек - 2, для 3 точек - 8:
Решается как-то через графы. Проверка: для 991 точки - ответ 948726690
Прошу прощения, я вероятно недопонял условия. Вот сам текст исходной задачи:
Given a number of vertices, determine the number of ways these vertices can form a graph. The graph may be disjoint, so it is not necessary to connect all vertices.The answer may be very large, return its value modulo (10**9+7). Note: Two ways of drawing edges are considered different if at least one pair of vertices has a different connection or the number of edges is different.
Спасибо за эти решения:
раз просто кол-во, то пусть они стоят по кругу. я думаю, что число ребер n=int(X*(X-1)/2), и тогда sum(f(n)/f(n-k)/f(k) for k in range(n+1)) – splash58 2 часа назад
Существует 2^(n*(n-1)/2) произвольных графов с n вершинами. Есть ощущение, что задача недопоставлена. – MBo 1 час назад
Осталась проблема переполнения стека для больших чисел на входе функции, как я понимаю, надо как-то разбивать вычисление на этапы и на каждом этапе выполнять операцию вида res = res % M, где M = 1000000000 + 7
Вот такое решение работает, но не проходит по лимиту времени:
MOD = (10**9 + 7)
def function(n):
level = int((n * (n - 1) / 2))
res = (2 ** level) % MOD
return int(res)
2^(n*(n-1)/2)
произвольных графов с n вершинами. Есть ощущение, что задача недопоставлена.