Given two number N and M as input find numbers such as:
-
The number should contain all the digits from 0 to N-1
-
The length of number can be atmost M i.e. it can have atmost M digits.
-
The difference between each adjacent digits should be one.
calculate the number of all such numbers.
Input
First line T : no. of test cases
For each test case: N M (space separated)
Output
For each test case no. of such numbers that can be formed using all 0-(N-1) digits and which have atmost M digits in single line.
Output should be in Modulo 1000000007
Constraints
0 ≤ t ≤ 100
2 ≤ N ≤ 10
0 ≤ M ≤ 500
(This Question was asked in Bytecode 2013 on Codechef. My head says Dynamic Programming, but I can’t think how to start about it.)
Let’s call strings that satisfy the condition of the task good. Also i’m going to index the string from 1, just for convenience.
Now let dp[i][j] be the number of good strings from 1st to i-th character such that the i-th character is j. It’s easy to deduce that:
dp[i][j] = dp[i - 1][j + 1] + dp[i - 1][j - 1] + dp[i - 1][j], for all 0 < j < n - 1
dp[i][0] = dp[i - 1][0] + dp[i - 1][1]
dp[i][n - 1] = dp[i - 1][n - 1] + dp[i - 1][n - 2]
Answer is the sum of dp[i][j], for all 0 <= j <= n - 1 and 1 <= i <= m.
Also first initialize dp[1][j] = 1, for all 0 <= j <= n - 1. Complexity of the above algorithm is O(M * N) per test case.
“number of good strings from 1st to i-th character such that the i-th character is j”? What does that mean?
Number of good strings of length i such that their last digit is j.
Example for n = 2.
dp[2][1] = 2, 01 and 11. (i = 2, j = 1)
dp[3][1] = 4, 001, 011, 101 and 111. (i = 3, j = 1)
How are these good strings? ‘11’, ‘011’, ‘111’ and ‘001’?
The difference between each adjacent digits should be one…
I implemented, doesn’t seem to work!