[superpermutat0r]

Here's a nice blog post about the algorithm 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.

[chillee]

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]

Please write a blog post!

[contravariant]

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.