|
|
|
|
|
|
by chillee
2242 days ago
|
|
|
Yes you can. Cayley Hamilton theorem gives a linear relation between A^N and the terms less than that. So for your problem, you can calculate the number of paths from A->B of length k in k*N^2 time, you need O(N^3) to compute enough terms for Berlekamp Massey, O(N^2) to compute Berlekamp Massey, and then O(n log n log k) to compute the k-th linear recurrence term with FFT. I've actually considered writing a blog post about this :) It's a cool example of how much further you can go with a problem where many people only know the O(NK)DP solution. |
|
|