All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
A pair of non-negative integers (A,B) is called and-pair if A & B = B, i.e., bitwise-and of A and B is equal to B. Similarly, a tuple of K non-negative integers (A1,A2,A3 .. AK) is called and-tuple if Ai & Ai+1 = Ai+1 for 1≤i≤K-1.
Given two integers N and K, how many and-tuples of size K exist such that the sum of the elements of the tuple is N?
First line contains T, the number of testcases, then T lines follow. Each of the following lines contain two space-separated integers K and N.
For each testcase, print a single line containing the answer. Since the number can be quite large, print the answer modulo 1000000009.
- In the first case, the two and-tuples are (2,0,0) and (1,1,0).
- In the second case they are (2,0,0,0) and (1,1,0,0).
|Tags||bit, dynamic-programming, easy-medium, ltime17, memoization, piyushkumar, recursion|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, 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, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.