Hi Guys, im doing a problem(474D). Problem I found this DP:

cnt = 1
i from 1 to 10^5:
 if(i < k)
    dp[i] = 1
 if(i == k)
    dp[i] = 2
 if(i > k)
    {
      if(i % k == 0)
         cnt++
      dp[i] += dp[i-1] + cnt
    }

the idea is :

let's k = 3

dp[1] = 1
dp[2] = 1
dp[3] = 2
----------
dp[4] = 3 
cause:
RRRR
RWWW
WWWR

dp[5]= 4
cause:
RRRRR
RRWWW
RWWWR
WWWRR

now, cnt = 2
dp[6] = 6
cause:
RRRRRR
RRRWWW
RRWWWR
RWWWRR
WWWRRR
WWWWWW

dp[7] = 8
dp[8] = 10

so that i do, is move the blocks of ( (1,2,3,...) * k ) * (white blocks) around the string. this is my code : http://mirror.codeforces.com/contest/474/submission/11493428 I dont know if my dp is wrong or is the MODULUS.

Thanks in Advance. :)