# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Name |
---|
You will have TLE because
T<=10^5
andb<=10^5
, your solution is O(T*(b-a)*(your recursion)).You have WA because you should add here
this
mem[x] %= MOD;
Use precalc to solve it.
thanks a lot...
I should learn one that you said
I didn't find anything can you help me?
Firstly we try change your recursive dp for linear (and we will pre calculate("precalc" or "pre calc") result in array to find next time by O(1)).
Now we can find fastly your dp(x) by d[x]
After this we must to find sum of all elements from
d[a]
tod[b]
we can do it by create a new array that will have
all sum from 1 to i(sum[i]=d[1]+...+d[i]) by precalc
then we know that answer for sum from
a
tob
like thiscout<<sum[b]-sum[a-1];
You can look for my code http://codeforces.net/contest/474/submission/9871904
Thank solved :D
Why you are creating new accounts
Cause I'm afraid of down votes...