Вычисление 1 ^ X + 2 ^ X +... + N ^ X mod 1000000007

Есть ли какой-либо алгоритм для вычисления (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

Вы можете подытожить серию

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).

Ответ 2

Существует несколько способов ускорения модульного возведения в степень. Отсюда я буду использовать ** для обозначения "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, мы просто имеем несколько повторяющихся сумм с "хвостом" частичного повторения.

Ответ 3

Я думаю, что ответ Ватины - это, вероятно, путь, но я уже набрал это и может быть полезно, для этого или для кого-то 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 до того, как я опубликовал.