All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Apurva is obsessed with Fibonacci numbers. She finds Fibonacci numbers very interesting. Fibonacci numbers can be defined as given below.
Fib(1) = 1 , Fib(2) = 1.
Fib(n) = Fib(n-1) + Fib(n-2) for n > 2 .
Given a set S having N elements and an integer K, She wants to find out the value of FIBOSUM(S).
Where sum(s) represents the sum of elements in set s.
Note that values might be repeated in the set, two subsets will be called different if there is an index i such that S[i] is occurring in one of the subset and not in another.
As the value of FIBOSUM(S) can be very large, print it modulo 99991.
- First line of input contains two integer N and K sepeated by a space.
- Next line contains N space separated integers denoting the set S.
Print a single integer representing the answer.
1 ≤ K ≤ N
Subtask #1: 10 points
- 1 ≤ N ≤ 20, 1 ≤ value in set ≤ 109
Subtask #2: 30 points
- 1 ≤ N ≤ 2000, 1 ≤ value in set ≤ 109
Subtask #3: 60 points
- 1 ≤ N ≤ 50000, 1 ≤ value in set ≤ 109
Input: 3 1 1 2 3 Output: 4
FIBOSUM(S) = Fib(1) + Fib(2) + Fib(3) = 4.
|Tags||amitpandeykgp, fft, june15, medium|
|Time Limit:||5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.