|
|
back to boardJust use DP, which is fast enough (AC 0.187s),
and works without using long arithmetics in O(30*n).
Only remember simple math theorems about mod, i. e.
(a+b) mod c = ((a mod c) + (b mod c)) mod c
(a-b) mod c = ((a mod c) - (b mod c)) mod c
(a*b) mod c = ((a mod c) * (b mod c)) mod c My brute-force solution got AC in 0.062s Brute force without big numbers?
I think that the most easy solution is that,
where long arithmetics not used. DP here? How? Oh, i've got...
Let's see... No, i have too slow AC :( 1.531
Can anyone explain DP? simple O(N) solution, 0.030s
You are completely right about using:
> (a*b) mod c = ((a mod c) * (b mod c)) mod c
Uses very facile DP technique like used[i] = true/false ;-) DP here? How? it`s knapsack problem please can anyone tell me how to solve this in briefly by bfs or dp...... I try DP but TLE #15, can send me your solution to my email : tungnk1993@gmail.com Tks You can achieve O(N) using bfs.
Edited by author 23.06.2009 21:23 I think it's nearer to bfs then DP |
|
|
