Exercise

题目描述:

Farmer John（又）想到了一个新的奶牛晨练方案！

如同之前，Farmer John 的 N 头奶牛（1≤N≤7500）站成一排。对于 1≤i≤N 的每一个 i，从左往右第 i 头奶牛的编号为 i。他告诉她们重复以下步骤，直到奶牛们与她们开始时的顺序相同。

 

• 给定长为 N 的一个排列 A，奶牛们改变她们的顺序，使得在改变之前从左往右第 i 头奶牛在改变之后为从左往右第 Ai 头。

例如，如果 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⁸≤M≤10⁹+7，M 是质数）。

使用 C++ 的选手可以使用 KACTL 中的这一代码。这一名为 Barrett 模乘 的算法可以以比通常计算快上数倍的速度计算 a%b，其中 b>1 为一个编译时未知的常数。（不幸的是，我们没有找到对于 Java 的这样的优化）。（译注：中文选手可以参考 几种取模优化方法（译自 min-25 的博客））

 

#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≤i≤N，以下序列的第 i 个元素等于奶牛需要使用 i 步的排列数量：[1,25,20,30,24,20]。所以答案等于 1¹⋅2²⁵⋅3²⁰⋅4³⁰⋅5²⁴⋅6²⁰≡369329541(mod109+7)。

时间限制: 1000ms
空间限制: 512MB

---

来源: USACO 2020 OPEN Platinum