9494. Just Add It

For two given integers n and k find

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

where Z_n = S_n + P_n, S_n = 1^k + 2^k + 3^k + ….. + n^k and P_n = 1¹ + 2² + 3³ + …… + nⁿ.

Input. There are several test cases. Each test case consists of one line with two space separated positive integers n and k (1 < n < 2*10⁸, 0 < k < 10⁶). The last test case contains two zeroes, which is not to be processed.

Output. For each case print the asked value in separate line.

Sample input	Sample output
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 + 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.io.*;

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

}

}

}