902. Permutation Powers

A permutation $\pi$$\pi$ of $\{1,\dots ,n\}$$\{1, \dots, n\}$ can be represented in one-line notation as $\pi (1),\dots ,\pi (n)$$\pi(1),\ldots,\pi(n)$. If all $n!$$n!$ permutations are written in lexicographic order then $\text{rank}(\pi )$$\textrm{rank}(\pi)$ is the position of $\pi$$\pi$ in this 1-based list.

For example, $\text{rank}(2,1,3)=3$$\text{rank}(2,1,3) = 3$ because the six permutations of $\{1,2,3\}$$\{1, 2, 3\}$ in lexicographic order are:

For a positive integer $m$$m$, we define the following permutation of $\{1,\dots ,n\}$$\{1, \dots, n\}$ with $n=\frac{m(m+1)}{2}$$n = \frac{m(m+1)}2$:

where ${\tau }^{-1}$$\tau^{-1}$ is the inverse permutation of $\tau$$\tau$.

Define ${\displaystyle P(m)=\sum _{k=1}^{m!}\text{rank}({\pi }^k)}$$\displaystyle P(m) = \sum_{k=1}^{m!} \text{rank}(\pi^k)$, where ${\pi }^k$$\pi^k$ is the permutation arising from applying $\pi$$\pi$ $k$$k$ times.
For example, $P(2)=4$$P(2) = 4$, $P(3)=780$$P(3) = 780$ and $P(4)=38810300$$P(4) = 38810300$.

Find $P(100)$$P(100)$. Give your answer modulo $({10}^9+7)$$(10^9 + 7)$.

902. 置换的幂

我们可以用 一行表示法 $\pi (1),\cdots ,\pi (n)$$\pi(1), \cdots, \pi(n)$ 表示 $\{1,2,\cdots ,n\}$$\{1, 2, \cdots, n\}$ 的一个排列 $\pi$$\pi$。我们将 $\{1,2,\cdots ,n\}$$\{1, 2, \cdots, n\}$ 的所有 $n!$$n!$ 个排列按字典序升序排序，放入下标从 $1$$1$ 开始的列表内，记 $\text{rank}(\pi )$$\textrm{rank}(\pi)$ 为 $\pi$$\pi$ 在这个列表中的位置。

例如，$\text{rank}(2,1,3)=3$$\text{rank}(2,1,3) = 3$。因为 $\{1,2,3\}$$\{1, 2, 3\}$ 的所有 $6$$6$ 个排列按字典序升序排序后的结果是：

对正整数 $m$$m$，令 $n=\frac{m(m+1)}{2}$$n = \frac{m(m + 1)}{2}$，我们定义如下 $\{1,\dots ,n\}$$\{1, \dots, n\}$ 的排列：

其中，${\tau }^{-1}$$\tau^{-1}$ 是 $\tau$$\tau$ 的逆置换。

记 ${\displaystyle P(m)=\sum _{k=1}^{m!}\text{rank}({\pi }^k)}$$\displaystyle P(m) = \sum_{k=1}^{m!} \text{rank}(\pi^k)$，其中 ${\pi }^k$$\pi^k$ 是 $\pi$$\pi$ 自身复合 $k$$k$ 次得到的排列。已知：$P(2)=4$$P(2) = 4$、$P(3)=780$$P(3) = 780$、$P(4)=38810300$$P(4) = 38810300$。

求 $P(100)$$P(100)$ 模 $({10}^9+7)$$(10^9 + 7)$ 的值。

点 这个链接 回到源站。

点 这个链接 回到详细版题目目录。