SPOJ.com - Problem ASUMHARD

ASUMHARD - A Summatory (HARD)

no tags

f(n) is defined as: f(n) = 1^k+2^k+3^k+ ... +n^k, 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

Warning: A naive algorithm may not run in time

Submit solution!

hide comments

< Previous 1 2 3 Next >

	Blasters: 2014-05-20 15:04:45 @Tjandra Can you please tell why i am getting tle ID NO 11612132 I used O(tk) + k^2 algo with fast i/o and on ideone the worst case runs in 4.5 sec Last edit: 2014-05-20 15:05:12*
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2014-02-09 22:57:40 @Francky: Congratulations :) Btw, Next valentine day (14th Febtuary 2014) I'll set new recurrence problem, It'll be my second hardest problem, I hope you'll like it.. ;) And welcome back to SPOJ, Francky, glad to 'see' you again..
	Francky: 2014-02-08 14:39:17 Fast IO bring me from 0.63 to 0.47, and first place. ;-). I liked work on this problem, I should have done the job before. About complexity : first part O(k^2) -> 0.00s, second part O(T×K) with a good constant : k/2 (modmul+add) per case. Now, it's 0.39s in C, but I need 1s or 2s to get AC in Py3. Last edit: 2014-02-08 18:02:33
	abdou_93: 2013-07-19 22:19:26 Why TLE ??!!!!!! Hint: Avoid repeated calculation. Last edit: 2013-07-20 08:01:13
	abdelkarim: 2013-07-16 01:59:11 by using Faulhaber's Triangle and some optimization i think i can solve this one in O(k^2) algo . Ans: good idea. Try it, I wonder how fast/slow your algo is.. My algo (when I publish this problem) using semi-naive idea, complexity is O(k^3) (without fast I/O (Because I don't know fast I/O trick at that time), run in just 2.03s)... Last edit: 2013-07-16 14:52:33
	Michael Kharitonov: 2013-03-07 08:11:21 Nice one, "Concrete Mathematics" rocks again! Finally beat Mitch ;-) Ans: Congratulations :-) now TJANDRA page has been updated ;-) Last edit: 2013-03-07 13:02:52
	15972125841321: 2012-07-22 14:36:18 @tajandra dude awesome problem had to optimize a whole lot of things to get an AC.. Ans: thanks.. btw, you're at #3 place now, good! Last edit: 2012-07-22 17:16:22
	TINYJR: 2012-07-13 14:45:34 I don't think k^2 is fast enough to AC this problem. Last edit: 2012-06-21 13:43:32
	devu: 2012-07-13 14:45:34 enjoyed solving it.. nice problem
	krishnan: 2012-07-13 14:45:34 How to approach this problem using Matrix exponentation. Can anyone give a hint. Thanks in Advance

Submit solution!

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.