首先考虑什么样的数组 a 符合条件，我们考虑一个贪心的思想，我们从前到后遍历，对于每一个 a_i 如果它已经在前面出现了就不断给它加 1 直到它没有出现过为止。如果某个 a_i 超过了 n 则不符合条件，正确性显然。这样看起来还是有点抽象，我们不妨把它转化成这样的模型：有一架飞机有 n 个位置，有 n 个乘客要登飞机，每个乘客都预定了一个位置 a_i，每个乘客上飞机的时候，如果它的位置已经被占了，那么它会一直向前走直到到达一个空位为止并坐下，如果有乘客没位置坐则不符合题意。
这是一个非常经典的问题，仿照那题的解法可以考虑这样的转化：添加一个 n+1 号位并接链成环（？），将原先在链上走转化为在环上走，那么 a 符合条件当且仅当 n+1 位置最后没有被占。由于这 n+1 个点组成一个环，故 n+1 个点是对称的，它们被占的概率都是相同的，为 \dfrac{1}{n+1}，因此合法的 a 的个数就是总序列数乘 \dfrac{1}{n+1}，即 (n+1)^{n-1}（注意：这里我们要做一个微调，即将 a_i 的上界扩大到 n+1，否则就无法保证每个点都是对称的了，这个 \dfrac{1}{n+1} 也就不成立了，故总序列个数实际上是 (n+1)^n，并且如果 \exists a_i=n+1 那么肯定就不合法了，因此你改就改呗，也不影响我合法的序列 a 的个数）。
到这里我们只分析完了序列 a 的性质，即将序列 a 的贡献全当作 1 来算后得到的答案，可实际上对于某个 a 它对答案的贡献并不是 1，而是 \sum\limits_{i=1}^{n+1}c_i^k，其中 c_i 为 i 的出现次数。这时候又到了动用咱们聪明才智的时候了。考虑继续分析 a 的性质，还是从「n+1 个点组成一个环」这个条件入手，显然我们将每个点都向右平移 C 格后每个数的出现次数不变，即合法的 b 的个数 cntb(a) 不变，但最后留下来的位置也会跟着平移 C 格。因此考虑对每个合法的序列 a 做 n 次映射，即 a_i:=(a_i+C-1)\bmod(n+1)+1，C=1,2,3,\cdots,n。由于 a 是合法的序列，故映射后的序列肯定不是合法序列，显然这 n+1 个序列的 cntb 都是相同的，又所有合法序列映射后肯定恰好包含全部序列，因此我们可以求出所有序列的答案之和后除以 n+1 即可算出答案。