How to solve this problem ? I cant even understand the sample input.

# Need help for this question #271 Div 2 D

**sdssudhu**#3

This is a DP problem. Since a and b can be atmost 10^5 and k is fixed you can precompute all values upto 10^5 . For i< k dp* is 1 and for i>=k you can add a R or W at the end. If you add R the previous value can be R or W.If you add a zero the previous k-1 must be zero for valid configuration. So

dp*=dp[i-1]+dp[k-1].