Exercise

题目描述

Farmer John 为奶牛们想出了一套新的晨练方案（又来了）！ 和之前一样，Farmer John 的 $N$ 头奶牛（$1\le N\le 7500$）排成一列站着。从左到右第 $i$ 头奶牛的编号为 $i$（对所有 $1\le i\le N$）。他让她们重复执行下面的步骤，直到奶牛的顺序回到最开始时的顺序。

给定一个长度为 $N$ 的排列 $A$，奶牛改变队形的方式是：变化前从左到右第 $i$ 头奶牛，在变化后会处在从左到右第 $A_i$ 个位置。

例如，如果 $A=(1,2,3,4,5)$，那么奶牛执行一步后会立刻回到相同的顺序。如果 $A=(2,3,1,5,4)$，那么奶牛会执行 6 步才回到原始顺序。每一步之后从左到右奶牛的顺序如下： 0 steps: $(1,2,3,4,5)$ 1 step: $(3,1,2,5,4)$ 2 steps: $(2,3,1,4,5)$ 3 steps: $(1,2,3,5,4)$ 4 steps: $(3,1,2,4,5)$ 5 steps: $(2,3,1,5,4)$ 6 steps: $(1,2,3,4,5)$

请计算对所有长度为 $N$ 的 $N!$ 种排列 $A$，所需步数的乘积。 由于该数可能非常大，请输出答案对 $M$ 取模的结果（$10^8\le M\le 10^9+7$，且 $M$ 为质数）。

使用 C++ 的选手可能会发现来自 KACTL 的如下代码有帮助。该方法称为 Barrett reduction，它可以让你在 $b>1$ 为常数但在编译期未知时，将计算 $a \% b$ 的速度提升数倍。（遗憾的是，我们不知道 Java 是否有类似优化。） #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$。

输出格式

输出一个整数。

5 1000000007

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}$。 Note: 本题的内存限制提升至 512 MB。 SCORING: 测试点 2 满足 $N=8$。 测试点 3-5 满足 $N\le 50$。 测试点 6-8 满足 $N\le 500$。 测试点 9-12 满足 $N\le 3000$。 测试点 13-16 没有额外限制。 题目出题人：Benjamin Qi

标签: USACO|2020|Platinum

来源

USACO|2020|Platinum