@vuvth plz share your approach. Do mail me at [email protected]
Solved in O(K). The new bricks are arranged in a number of contiguous groups, between 1 and K such groups. For any one such value g of the number of groups, there will be \binom{k-1}{g-1} ways of splitting up the new bricks and \binom{n-k+1}{g} of inserting those groups into the path. Each group can be laid 2 ways of course, left- or right-hand start, so there is also a factor of 2^g.
Then iterate from g=1 up to g=k (or g=n-k+1 if smaller), updating the binomial coefficients stepwise rather than recalculating, using modular inverses up to 1000 which are precalculated.
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.