1 //Accepted    368K    532MS 2 //线性dp 3 //dp[i][j]表示前i位最后一个是j的排列数 4 //dp[i][j]=sum(dp[i-1][h])  h*2<=j 5 #include <cstdio> 6 #include <cstring> 7 #include <iostream> 8 using namespace std; 9 const int imax_n = 15;10 const int imax_m = 2005;11 __int64 dp[imax_n][imax_m];12 int n,m;13 void Dp()14 {15     memset(dp,0,sizeof(dp));16     for (int i=1;i<=m;i++)17     dp[1][i]=1;18     for (int i=2;i<=n;i++)19     {20         for (int j=1<<(i-1);j<=m;j++)21         {22             dp[i][j]=0;23             for (int k=1<<(i-2);2*k<=j;k++)24             {25                 dp[i][j]+=dp[i-1][k];26             }27         }28     }29 }30 int main()31 {32     int T;33     scanf("%d",&T);34     for (int t=1;t<=T;t++)35     {36         scanf("%d%d",&n,&m);37         Dp();38         __int64 ans=0;39         for (int i=1<<(n-1);i<=m;i++)40         ans+=dp[n][i];41         printf("Case %d: n = %d, m = %d, # lists = %I64d\n",t,n,m,ans);42     }43     return 0;44 }