[USACO20OPEN]Exercise P

题目描述

Farmer John(又)想到了一个新的奶牛晨练方案! 如同之前,Farmer John 的 $N$ 头奶牛站成一排。对于 $1\le i\le N$ 的每一个 $i$,从左往右第 $i$ 头奶牛的编号为 $i$。他告诉她们重复以下步骤,直到奶牛们与她们开始时的顺序相同。 给定长为 $N$ 的一个排列 $A$,奶牛们改变她们的顺序,使得在改变之前从左往右第 $i$ 头奶牛在改变之后为从左往右第 $A_i$ 头。 例如,如果 $A=(1,2,3,4,5)$,那么奶牛们总共进行一步就回到了同样的顺序。如果 $A=(2,3,1,5,4)$,那么奶牛们总共进行六步之后回到起始的顺序。每步之后奶牛们从左往右的顺序如下: 0 步:$(1,2,3,4,5)$ 1 步:$(3,1,2,5,4)$ 2 步:$(2,3,1,4,5)$ 3 步:$(1,2,3,5,4)$ 4 步:$(3,1,2,4,5)$ 5 步:$(2,3,1,5,4)$ 6 步:$(1,2,3,4,5)$ **请你计算出所有可能的 $N!$ 种长为 $N$ 的排列 $A$ 回到起始顺序需要的步数的乘积。** 由于这个数字可能非常大,输出答案模 $M$ 的余数($10^8\le M\le 10^9+7$,$M$ 是质数)。 ----- 使用 C++ 的选手可以使用 [KACTL](https://github.com/kth-competitive-programming/kactl/blob/master/content/various/FastMod.h) 中的这一代码。这一名为 [Barrett 模乘](https://en.wikipedia.org/wiki/Barrett_reduction) 的算法可以以比通常计算快上数倍的速度计算 $a \% b$,其中 $b>1$ 为一个编译时未知的常数。(不幸的是,我们没有找到对于 Java 的这样的优化)。(译注:中文选手可以参考 几种取模优化方法[(译自 min-25 的博客)](https://loj.ac/article/327)) ```cpp #include <bits/stdc++.h> using namespace std; typedef unsigned long long ull; typedef __uint128_t L; struct FastMod { ull b, m; FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {} ull reduce(ull a) { ull q = (ull)((L(m) * a) >> 64); ull r = a - q * b; // can be proven that 0 <= r < 2*b return r >= b ? r - b : r; } }; FastMod F(2); int main() { int M = 1000000007; F = FastMod(M); ull x = 10ULL*M+3; cout << x << " " << F.reduce(x) << "\n"; // 10000000073 3 } ```

输入输出格式

输入格式


输入一行包含 $N$ 和 $M$。

输出格式


输出一个整数。

输入输出样例

输入样例 #1

5 1000000007

输出样例 #1

369329541

说明

#### 样例解释: 对于每一个 $1\le i\le N$,以下序列的第 $i$ 个元素等于奶牛需要使用 $i$ 步的排列数量:$[1,25,20,30,24,20]$。所以答案等于 $1^1\cdot 2^{25}\cdot 3^{20}\cdot 4^{30}\cdot 5^{24}\cdot 6^{20}\equiv 369329541\pmod{10^9+7}$。 **注意:这个问题的内存限制增加为 512 MB。** --- 对于 $100\%$ 的数据,满足 $1\le N\le 7500$。 共 $16$ 个测试点,其中 $1$ 为样例,其余性质如下: 测试点 $2$ 满足 $N=8$。 测试点 $3\sim 5$ 满足 $N\le 50$。 测试点 $6\sim 8$ 满足 $N\le 500$。 测试点 $9\sim 12$ 满足 $N\le 3000$。 测试点 $13\sim 16$ 没有额外限制。 ---- 出题人:Benjamin Qi