A-E Hash Function
All submissions for this problem are available.
Chef Ash and Chef Elsh invented a new hash function! Their hash function will map a binary string consisting of characters 'A' and 'E' into an integer called the hash value of the string.
The pseudocode of the hash function is as below. hash(S) is the hash value of a binary string S. |S| denotes the length of S.
function hash(S): result = number of characters 'A' in S if |S| > 1: (S1, S2) = split(S) result = result + max(hash(S1), hash(S2)) end if return result end function
The function split in the above pseudocode takes a binary string S as the parameter and returns a pair of binary strings (S1, S2) such that:
- |S1| <= |S2|.
- The difference of |S1| and |S2| is at most 1.
- The concatenation of S1 and S2 (in that order) is S.
For example, split("AAAEE") returns ("AA", "AEE"), whereas split("AEAEAE") returns ("AEA", "EAE").
You doubt that this hash function have good distribution of different hash values. So, you wonder how many different binary strings consisting of A 'A' characters and E 'E' characters that have hash value of V.
The first line contains a single integer T, the number of test cases. T test cases follow. Each testcase consists of a single line consisting of three integers A, E, and V.
For each test case, output a single line consisting the number of different binary strings satisfying the rule, modulo 1000000007.
- 1 ≤ T ≤ 1000
- 0 ≤ A ≤ 50
- 0 ≤ E ≤ 50
- 0 ≤ V ≤ 1000
Input: 4 0 0 0 1 0 1 3 2 6 4 2 8 Output: 1 1 3 4
For the last test case, the solutions are:
|Tags||easy, fushar, july11|
|Time Limit:||0.286613 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, 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, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.