#PU1045. USACO 2020 US Open Contest, Platinum — Problem 2. Exercise
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 cows () are standing in a line. The -th cow from the left has label for each . He tells them to repeat the following step until the cows are in the same order as when they started. Given a permutation of length , the cows change their order such that the -th cow from the left before the change is -th from the left after the change. For example, if then the cows perform one step and immediately return to the same order. If , 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 step: 2 steps: 3 steps: 4 steps: 5 steps: 6 steps: Compute the product of the numbers of steps needed over all possible permutations of length . As this number may be very large, output the answer modulo (, is prime). Contestants using C++ may find the following code from KACTL helpful. Known as the Barrett reduction , it allows you to compute several times faster than usual, where 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 and .
输出格式
A single integer.
数据范围
Test case 2 satisfies . Test cases 3-5 satisfy . Test cases 6-8 satisfy . Test cases 9-12 satisfy . 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}$.