Problem
Lenny likes to play the game of lotto. In the lotto game, he picks a list of N unique numbers in the range from 1 to M. If his list matches the list of numbers that are drawn, he wins the big prize.
Lenny has a scheme that he thinks is likely to be lucky. He likes to choose his list so that each number in it is at least twice as large as the one before it. So, for example, if N = 4 and M = 10, then the possible lucky lists Lenny could like are:
1 2 4 8
1 2 4 9
1 2 4 10
1 2 5 10
Thus Lenny has four lists from which to choose.
Your job, given N and M, is to determine from how many lucky lists Lenny can choose.
Input
There will be multiple cases to consider from input. The first input will be a number C (0 < C <= 50) indicating how many cases with which you will deal. Following this number will be pairs of integers giving values for N and M, in that order. You are guaranteed that 1 <= N <= 10, 1 <= M <= 2000, and N <= M. Each N M pair will occur on a line of its own. N and M will be separated by a single space.
Output
For each case display a line containing the case number (starting with 1 and increasing sequentially), the input values for N and M, and the number of lucky lists meeting Lenny’s requirements. The desired format is illustrated in the sample shown below.
Sample Input
3 4 10 2 20 2 200
Sample Output
Case 1: n = 4, m = 10, # lists = 4 Case 2: n = 2, m = 20, # lists = 100 Case 3: n = 2, m = 200, # lists = 10000
简单DP，f[i][j]表示分为i个数，且最大数为j时的最多方案数，则可以得到递推公式f[i][j]=∑f[i-1][k](k∈[1..j/2])
在这个公式下时间复杂度应该是O（nm2），虽然可以0.71s过，但是时间还是很长，其实有个点是比较容易发现的，就是f[i][j]和f[i][j-1]的差别其实是很小的，而且差值和j有关系，但j为偶数的时候两者相差f[i-1][j/2]，当j为奇数时，两者相同，这样的话就可以将复杂度降为O（nm），可以0.01s过～
附上代码（很短的）：