题意：太难翻译了。。。只可意会，不可言传。。。

题解：dp[i][j]为长度为i且含j个不同节拍的方法种数，那么dp[i][j]=dp[i-1][j-1]+dp[i-1][j]*j，即多出的节拍独自一种或者与前面某种相同。后来证实，这就是第二类string数

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 double dp[100][100]; 6 int main() 7 { 8     memset(dp,0,sizeof(dp)); 9     dp[0][0]=1;10     for(int i=1;i<100;i++)11     {12         for(int j=1;j<=i;j++)13             dp[i][j]=dp[i-1][j]*j+dp[i-1][j-1];14     }15     int n;16     while(scanf("%d",&n),n)17     {18         double ans=0;19         for(int i=1;i<=n;i++)20             ans+=dp[n][i];21         printf("%d %.0lf\n",n,ans);22     }23     return 0;24 }