If you have a collection of DP problems, it may interest you to look through this: 3144 Live Archive.
Let me explain my reasoning:
for given m let c[m][n][v] be the number of all sequences of length n with v being its first element.
then we get the following recurrence:
Code: Select all
c[m][n][v] = c[m][n-1][2*v] + c[m][n-1][2*v+1] + ... + c[m][n-1][m]
and the answer is, therefore, c[m][n][1] + c[m][n][2] + ... + c[m][n][m].
TLE. What do you say?