There is a function called "the one function",
the function is defined as:
F(N, M) = 1, if M <= N,
F(N, M) = F(N, M-1) + F(N, M - 2) + ... + F(N, M - N), if M > N
Given you N, M, tell the result of F(N, M) module 1000000009.
ouo.
Updated at: 2020/05/17 19:00, sorry for the typo in the description.
This is an exercise of operator overloading,
it is recommended that you can follow the partial judge code to finish your work.
There are 8 member functions and 1 additional function that you should implement.
Read the comments carefully to better understand the structure of the partial judge code.
You should choose 'c++11' as the option of submission.
For sample input 1,
N = 3, M = 5,
so F(3, 1) = F(3, 2) = F(3, 3) = 1,
and F(3, 4) = F(3, 3) + F(3, 2) + F(3, 1) = 3
and F(3, 5) = F(3, 4) + F(3, 3) + F(3, 2) = 5
and F(3, 5) % 100000009 = 5,
so the output must be 5.
The input contains 1 line,
the first line contains 2 numbers N, M.
It is guaranteed that:
1 <= N <= 100
1 <= M <= 10^9
The output contains 1 line.
Output the answer of F(N, M), and a newline character at the end of line.