this is cool, do you mind explaining your solution ?
1 Like
I edited that part.
3 Likes
Yes it can be solved using Matrix exponentiation.
Links:
https://discuss.codechef.com/questions/137810/bbricks-editorial?page=1#137989
Yes it can be solved using Matrix exponentiation.
Links:
https://discuss.codechef.com/questions/137810/bbricks-editorial?page=1#137989
Assume T(n) = dp(n, n) * x^n + dp(n, n - 1) * x^(n - 1) + … + dp(n, 0) * x^0
=> T(n) = (x + 1)T(n - 1) + xT(n - 2).
We want dp(N, K) with K <= 1000 so we store first (K + 1) first element of T(n) and calculate on this.
Use Matrix exponentiation
[T(n) T(n - 1)] |(x +1) 1| = [T(n + 1) T(n)]
| x 0|
Cost for multiplication two matrix is O(8 * K ^ 2).
Sorry for my english. Happy coding <3.