5493. Просто просуммируйте

Для заданных целых чисел n и k найдите

(Z_n + Z_n-1 – 2Z_n-2) mod 10000007,

где Z_n = S_n + P_n, S_n = 1^k + 2^k + 3^k + ….. + n^k и P_n = 1¹ + 2² + 3³ + …… + nⁿ.

Вход. Состоит из нескольких тестов. Каждый тест состоит из одной строки, содержащей два положительных целых числа n и k (1 < n < 2*10⁸, 0 < k < 10⁶). Последний тест содержит два нуля и не обрабатывается.

Выход. Для каждого теста выведите ответ в отдельной строке.

Пример входа	Пример выхода
10 3 9 31 83 17 5 2 0 0	4835897 2118762 2285275 3694

РЕШЕНИЕ

математика + рекурсия

Анализ алгоритма

Упростим требуемое выражение:

Z_n + Z_n-1 – 2Z_n-2 = S_n + S_n-1 – 2 * S_n-2 + P_n + P_n-1 – 2* P_n-2 =

(1^k + 2^k + 3^k + ….. + n^k) + (1^k + 2^k + 3^k + ….. + (n – 1)^k) –

2*(1^k + 2^k + 3^k + ….. + (n – 2)^k) + (1¹ + 2² + 3³ + …… + nⁿ) +

(1¹ + 2² + 3³ + …… + (n – 1)^n-1) – 2*(1¹ + 2² + 3³ + …… + (n – 2)^n-2) =

= n^k + 2(n – 1)^k + nⁿ + 2(n – 1)^n-1

Остается вычислить сумму четырех слагаемых, взятую по модулю 10000007.

Реализация алгоритма

Объявим константу MOD, равную 10000007.

#define MOD 10000007

Функция PowMod возвращает значение xⁿ mod MOD .

long long PowMod(long long x, long long n)

{

if (!n) return 1;

if (n & 1) return (x * PowMod((x * x) % MOD, n / 2)) % MOD;

return PowMod((x * x) % MOD, n / 2);

}

Основная часть программы. Для каждой пары чисел n и k вычисляем сумму n^k + 2(n – 1)^k + nⁿ + 2(n – 1)^n-1 по модулю MOD.

while(scanf("%lld %lld",&n,&k), n + k)

{

res = (PowMod(n,k) + 2*PowMod(n-1,k) + PowMod(n,n) +

2*PowMod(n-1,n-1)) % MOD;

printf("%d\n",res);

}

Java реализация

import java.util.*;

public class Main

{

private final static long MOD = 10000007;

static long PowMod(long x, long n)

{

if (n == 0) return 1;

if (n % 2 == 1) return (x * PowMod((x * x) % MOD, n / 2)) % MOD;

return PowMod((x * x)% MOD, n / 2);

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

while(true)

{

long n = con.nextLong();

long k = con.nextLong();

if (n + k == 0) break;

long res = (PowMod(n,k) + 2*PowMod(n-1,k) +

PowMod(n,n) + 2*PowMod(n-1,n-1)) % MOD;

System.out.println(res);

}

con.close();

}

}