ASUMHARD - A Summatory (HARD)
f(n) is defined as: f(n) = 1k+2k+3k+ ... +nk, so it is the sum of the k-th power of all natural numbers up to n.
In this problem you are about to compute,
f(1) + f(2) + f(3) + ... + f(n)
Input
The first line is an integer T (1 ≤ T ≤ 54,321), denoting the number of test cases. Then, T test cases follow.
For each test case, there are two integers n (1 ≤ n ≤ 123,456,789) and k (0 ≤ k ≤ 321) written in one line, separated by space.
Output
For each test case output the result of the summatory function described above.
Since this number could be very large, output the answer modulo 1,234,567,891.
Example
Input: 5
2 3
10 3
3 3
100 0
100 1 Output: 10
7942
46
5050
171700
Warning: A naive algorithm may not run in time
hide comments
|
Mitch Schwartz:
2012-07-13 14:45:34
@Tjandra: Thanks, I enjoyed working on the problem. :) |
|
RAJDEEP GUPTA:
2012-07-13 14:45:34
I think this can be solved by matrix exponentiation. But what is the size of the matrix? I can't think of any matrix of reasonable size. :O |
|
(Tjandra Satria Gunawan)(曾毅昆):
2012-07-13 14:45:34
@Mitch Schwartz : Congratulations! :-D |
| Added by: | Tjandra Satria Gunawan |
| Date: | 2012-06-07 |
| Time limit: | 2.107s |
| Source limit: | 12345B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM32-GCC ASM64 MAWK BC C-CLANG NCSHARP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET |
| Resource: | Harder version of A Summatory problem. |
RSS