Упражнение (Платина)
Фермер Джон (снова) придумал новый режим утренней зарядки для коров!
Как и прежде, n коров фермера Джона выстроились в линию. i - ая корова слева имеет метку i для каждого i (1 ≤ i ≤ n). Он говорит им повторять следующий шаг до тех пор, пока коровы не будут в том же порядке, что и при старте.
Дана перестановка A длины n, коровы меняют свой порядок так, что 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! возможных перестановок A длины n.
Поскольку это число может быть очень большим, выведите ответ по модулю m.
Участники, использующие C++, могут найти следующий код из KACTL полезным. Известный как редукция Барретта, он позволяет вычислять a % b в несколько раз быстрее обычного, где b > 1 константа, неизвестная во время компиляции (к сожалению, нам не известно о такой оптимизации для 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 (1 ≤ n ≤ 7500) и m (10^8 ≤ m ≤ 10^9 + 7, m простое).
Выходные данные
Выведите одно число.
Пример
Для каждого i (1 ≤ i ≤ n), i - ый элемент следующего массива - это количество перестановок, которые заставляют коров делать i шагов: [1, 25, 20, 30, 24, 20]. Ответ равен 1^1 * 2^25 * 3^20 * 4^30 * 5^24 * 6^20 = 369329541 (mod 10^9 + 7).