Typical DP problem when N is small.
In this problem, N can be as large as 10^9, so matrix multiplication should be used. Unlike the problem I've done before, this time the matrix is as large as 16x16 (because there is 2^4 number of states at each layer). I write code to pre-generate the 16x16 matrix instead of hard-coding the formula, and then do matrix multiplication as usual.
沒有留言:
張貼留言