Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### joaquingc123's blog

By joaquingc123, history, 5 years ago, ,

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://codeforces.com/contest/474/submission/11493428 I dont know if my dp is wrong or is the MODULUS.