Есть ли какой-либо алгоритм для вычисления (1^x + 2^x + 3^x + ... + n^x) mod 1000000007?
Примечание: a^b - это b-я степень.
Ограничения 1 <= n <= 10^16, 1 <= x <= 1000. Таким образом, значение N очень велико.
Я могу решить только для O(m log m), если m = 1000000007. Это очень медленно, потому что ограничение времени составляет 2 секунды.
Есть ли у вас эффективный алгоритм?
Был комментарий, что это может быть дубликат этого вопроса, но это определенно отличается.
Вы можете подытожить серию
1**X + 2**X + ... + N**X
с помощью Faulhaber formula и вы получите полином с мощностью X + 1 для вычисления для произвольного N.
Если вы не хотите вычислять числа Бернулли, вы можете найти многочлен, решая линейные уравнения X + 2 (для N = 1, N = 2, N = 3, ..., N = X + 2), который является более медленным методом, но более простым в реализации.
Приведем пример для X = 2. В этом случае мы имеем полином порядка X + 1 = 3:
A*N**3 + B*N**2 + C*N + D
Линейные уравнения
A + B + C + D = 1 = 1
A*8 + B*4 + C*2 + D = 1 + 4 = 5
A*27 + B*9 + C*3 + D = 1 + 4 + 9 = 14
A*64 + B*16 + C*4 + D = 1 + 4 + 9 + 16 = 30
Решив уравнения, получим
A = 1/3
B = 1/2
C = 1/6
D = 0
Последняя формула
1**2 + 2**2 + ... + N**2 == N**3 / 3 + N**2 / 2 + N / 6
Теперь вам нужно всего лишь положить произвольную большую N в формулу. Пока алгоритм имеет сложность O(X**2) (поскольку он не зависит от N).
Существует несколько способов ускорения модульного возведения в степень. Отсюда я буду использовать ** для обозначения "exponentiate" и % для обозначения "модуля".
(a * b) % m ((a % m) * (b % m)) % m
. Также всегда бывает, что a ** n совпадает с (a ** floor(n / 2)) * (a ** (n - floor(n/2)). Это означает, что при экспоненте <= 1000 всегда можно завершить возведение в не более чем 20 умножений (и 21 мода).
Мы также можем пропустить несколько расчетов, так как (a ** b) % m совпадает с ((a % m) ** b) % m, а если m значительно меньше n, мы просто имеем несколько повторяющихся сумм с "хвостом" частичного повторения.
Я думаю, что ответ Ватины - это, вероятно, путь, но я уже набрал это и может быть полезно, для этого или для кого-то elses похоже проблема.
У меня нет времени этим утром для подробного ответа, но подумайте об этом.
1^2 + 2^2 + 3^2 + ... + n^2 будет принимать O (n) шаги для вычисления непосредственно.
Однако его эквивалент (n(n+1)(2n+1)/6), который может быть вычислен в
O (1). Аналогичная эквивалентность существует для любой более высокой интегральной мощности
х.
Может быть общее решение таких проблем; Я не знаю одного, и Wolfram Alpha, похоже, не знает об этом. Однако в общее эквивалентное выражение имеет степень x + 1 и может быть обработано путем вычисления некоторых выборочных значений и решения набора линейных уравнения для коэффициентов.
Однако это было бы трудно для больших x, например 1000, как в вашем проблема, и, вероятно, не может быть сделано в течение 2 секунд.
Возможно, тот, кто знает больше математики, чем я, может превратить это в работоспособное решение?
Edit: Упс, я вижу, что Fabian Pijcke уже опубликовал полезную ссылку о Формуле Faulhaber до того, как я опубликовал.