我们先来回顾和学习一些组合数学的知识。

如果给n个数，那么用这些数可以构成的全排列的种类是```n!```. 比如n=3时，全排列有6个，123,132,213,231,312,321.

将某个排列首尾相接，如果元素种类相同、元素的相对顺序相同，那么就是同一个“环排列”。

如果有n个数，能够组成的不同的环排列的个数是```n!/n = (n-1)!```。这是因为一个环排列，按照首元素的不同，可以拆分为n个全排列。所以环排列是全排列的“去重”版本。

比如n=3时，环排列只有2个，123 (231,312), 132 (231 231)。

此外，我们还可以发现，环排列的个数，其实等价于你固定一个“全排列的首元素”，然后其余的元素随机摆放。

高中数学的全排列公式 ```A(n,m) = n!/(n-m)!```

基于全排列公式再去重 ```A(n,m) = n!/(n-m)!/m!```

令dp[i][j]表示从前i个数里面构造j个全排列。考虑第i个数：

1. 第j个数自己构成一个新的全排列，方案数等同于```dp[i-1][j-1]```

2. 前i-1个数已经构成了j个全排列，那么第i个数可以插入这j个全排列的任意位置(中间加两边)，总共有i-1+j个位置。即```dp[i-1][j]*(i-1+j)```

综上递推公式 ```dp[i][j] = dp[i-1][j-1] + dp[i-1][j]*(i-1+j)```

令dp[i][j]表示从前i个数里面构造j个环排列。考虑第i个数：

1. 第j个数自己构成一个新的环排列，方案数等同于```dp[i-1][j-1]```

2. 前i-1个数已经构成了j个环排列，那么第i个数可以插入这j个环排列的任意位置(环没有两边的概念)，总共有i-1个位置。即```dp[i-1][j]*(i-1)```

从n个数里构造m个环排列，这样的方案数叫做第一类斯特林数，递推公式即 ```S1[i][j] = S1[i-1][j-1] + S1[i-1][j]*(i-1)```。

本题的本质就是求如何在n个数里构造k个环排列，即S[n][k]。为什么呢？我们将符合要求的排列分为k个区间：``` [a1, x ... x], [a2, x .. x], ... [ak, x...x]```，其中ai就是那些可见的柱子，并且是各自区间内的最大值，且```a1<a2<a3<..<ak```。

无论你如何将n个数分成k个区间，每个区间都有最大值，且这些最大值之间也可以按大小排序。所以任何分成k个区间的方案，都可以写成上面的形式```[a1, x ... x], [a2, x .. x], ... [ak, x...x]```。并且每个区间的方案数就是环排列的方案数，这是因为你需要固定每个区间的首元素（最大的），而区间剩下的元素可以任意摆放（见前文）。这样得到的排列都是都是distinct的环排列。