Just 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 ;-)

You can achieve O(N) using bfs.

Edited by author 23.06.2009 21:23

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

I think it's nearer to bfs then DP