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  ?

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

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