AC代码

https://codeforces.com/contest/1768/submission/188646233

题意：

考虑长度为3n的置换p。每次可以执行以下操作之一：

1.按递增顺序排序前2n个元素。

2.按递增顺序对最后2n个元素进行排序。

我们可以证明，仅使用这些操作就可以使每个排列按递增顺序排序。

让我们称f(p)为使排列p按递增顺序排序所需的这些操作的最小数目。

给定n，求f(p)的和，对所有(3n)！个长度为3n的排列p。

由于答案可能非常大，所以将其模素数M输出。

题解：

组合数学 + 数论