#PU1045. USACO 2020 US Open Contest, Platinum — Problem 2. Exercise

    ID: 1610 传统题 文件IO:exercise 2000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:open20来源:usaco.orgscoring:equal_test_cases数学

USACO 2020 US Open Contest, Platinum — Problem 2. Exercise

USACO 2020 US Open Contest, Platinum — Problem 2. Exercise

题目描述

Farmer John has come up with a new morning exercise routine for the cows (again)! As before, Farmer John's NN cows (1≤N≤75001\le N\le 7500) are standing in a line. The ii-th cow from the left has label ii for each 1≤i≤N1\le i\le N. He tells them to repeat the following step until the cows are in the same order as when they started. Given a permutation AA of length NN, the cows change their order such that the ii-th cow from the left before the change is AiA_i-th from the left after the change. For example, if A=(1,2,3,4,5)A=(1,2,3,4,5) then the cows perform one step and immediately return to the same order. If A=(2,3,1,5,4)A=(2,3,1,5,4), then the cows perform six steps before returning to the original order. The order of the cows from left to right after each step is as follows: 0 steps: (1,2,3,4,5)(1,2,3,4,5) 1 step: (3,1,2,5,4)(3,1,2,5,4) 2 steps: (2,3,1,4,5)(2,3,1,4,5) 3 steps: (1,2,3,5,4)(1,2,3,5,4) 4 steps: (3,1,2,4,5)(3,1,2,4,5) 5 steps: (2,3,1,5,4)(2,3,1,5,4) 6 steps: (1,2,3,4,5)(1,2,3,4,5) Compute the product of the numbers of steps needed over all N!N! possible permutations AA of length NN. As this number may be very large, output the answer modulo MM (108≤M≤109+710^8\le M\le 10^9+7, MM is prime). Contestants using C++ may find the following code from KACTL helpful. Known as the Barrett reduction , it allows you to compute a%ba \% b several times faster than usual, where b>1b>1 is constant but not known at compile time. (we are not aware of such an optimization for Java, unfortunately). #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 }

输入格式

The first line contains NN and MM.

输出格式

A single integer.

数据范围

Test case 2 satisfies N=8N=8. Test cases 3-5 satisfy N≤50N\le 50. Test cases 6-8 satisfy N≤500N\le 500. Test cases 9-12 satisfy N≤3000N\le 3000. Test cases 13-16 satisfy no additional constraints. Problem credits: Benjamin Qi

样例

样例 1

5 1000000007
369329541
For each $1\le i\le N$, the $i$-th element of the following array is the number
of  permutations that cause the cows to take $i$ steps: $[1,25,20,30,24,20].$
The answer  is
$1^1\cdot 2^{25}\cdot 3^{20}\cdot 4^{30}\cdot 5^{24}\cdot 6^{20}\equiv 369329541\pmod{10^9+7}$.