Discussion @ 1013. K-based Numbers. Version 3 @ Timus Online Judge

How can I pass the time limit ? Please help me !!!

Posted by Nguyen Viet Bang 25 Aug 2002 15:26

The algorithms I found requires O(N^2) , which N = 1800 . But we
must calculate the large-number ( I use string) , so it takes about O
(N^3) !!! . Could anyone help me on this Problem ?

Re: How can I pass the time limit ? Please help me !!!

Posted by Renat Mullakhanov 25 Aug 2002 19:38

There is O(N) algorithm based on formula: f(n)=(k-1)*(f(n-2)+f(n-1)).

Some hint

Posted by Zhou Yiyan@SHU 27 Aug 2002 18:03

1 Don't use string, use int array.
2 use larger base to reduce the total operation
3 if C++, don't use STL

Discussion of Problem 1013. K-based Numbers. Version 3