reference/name for this (maybe related to DP or LP)

Hi, in some problems an acquaintance solves some problems from the ICPC by associating a matrix to certain values of a function and then he obtains the final answer after taking the exponential of the matrix to some power and looking at some value of the matrix (e.g. A[0][0] or A[1][n] or something).

May someone give me a reference for this? what’s the name of this technique? Sorry for not being more accurate but it’s all I know/understand. Thanks in advance.

Hello,

What you describe seems to be the Matrix Exponentiation Technique, which is very useful! :slight_smile:

You can read more about it on the above link, which is a sort of tutorial I did and also here.

Best regards,

Bruno Oliveira

1 Like

Very nice tutorial. Where else can I find more about that? :slight_smile:

Hello @cybuster,

I guess that there are some places online which describe this technique in some detail, it’s easy to find them on Google and alike search engines, but, if you search here for the tag matrix-expo I’m sure you will be able to find some really good problems on this :smiley:

Best regards,

Bruno

1 Like