4 ms·

> You can more easily generalize this solution to other arithmetic sequences. Fun trick, if you ever find yourself in a situation like this - instead of calcul

> You can more easily generalize this solution to other arithmetic sequences. Fun trick, if you ever find yourself in a situation like this - instead of calculating the matrix by hand (a tedious chore), you can use an algorithm called Berlekamp Massey on the terms of your sequence and then find the k-th term in O(N log N log K) time instead of O(N^3 log K) time (like matrix exponentiation would).

deleted 6y ago
[deleted]
superpermutat0r 6y ago
Here's a nice blog post about the algorithm https://codeforces.com/blog/entry/61306 https://codeforces.com/blog/entry/61306 . It definitely makes sense, recurrence relation does have its own polynomial. Even the naive polynomial multiplication is very fast. Now, what I'm wondering is if this is possible to do with adjacency matrices of graphs. Recently I was calculating the number of paths of a knight going from one position to another in K moves. Ended up doing O(N^6 log K) (N is the chessboard dimension) which was fast enough for a small chessboard but maybe there's a way to turn that adjacency matrix to a polynomial and do the same.
- contravariant 6y ago
  On an unbounded chessboard it's not too difficult to represent the movement of a knight by a polynomial (or really a 2D convolution), but when your chessboard is bounded then the boundary effects become annoying. Maybe there is some way to mitigate those but I'm not aware of any.
- chillee 6y 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.
  - mrgriffin 6y ago
    Please write a blog post!

deleted 6y ago

[deleted]

superpermutat0r 6y ago

Here's a nice blog post about the algorithm https://codeforces.com/blog/entry/61306 https://codeforces.com/blog/entry/61306 . It definitely makes sense, recurrence relation does have its own polynomial. Even the naive polynomial multiplication is very fast. Now, what I'm wondering is if this is possible to do with adjacency matrices of graphs. Recently I was calculating the number of paths of a knight going from one position to another in K moves. Ended up doing O(N^6 log K) (N is the chessboard dimension) which was fast enough for a small chessboard but maybe there's a way to turn that adjacency matrix to a polynomial and do the same.

contravariant 6y ago
On an unbounded chessboard it's not too difficult to represent the movement of a knight by a polynomial (or really a 2D convolution), but when your chessboard is bounded then the boundary effects become annoying. Maybe there is some way to mitigate those but I'm not aware of any.
chillee 6y 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.
- mrgriffin 6y ago
  Please write a blog post!