RiseOJ – 운동

설명

농부 존이 (또다시) 소들을 위한 새로운 아침 운동 루틴을 고안했다!

이전처럼 농부 존의 소 $$N$$ 마리( $1\le N\le 7500$ )가 한 줄로 서 있다. 왼쪽에서 $$i$$ 번째 소는 각 $1\le i\le N$ 에 대해 번호 $$i$$ 를 가지고 있다. 그는 소들에게 처음과 같은 순서가 될 때까지 다음 단계를 반복하라고 지시한다.

길이 $$N$$ 의 순열 $$A$$ 가 주어졌을 때, 소들은 바꾸기 전 왼쪽에서 $$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$$ 의 가능한 모든 $$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
}

문제 제공: Benjamin Qi

제약

배점

테스트 케이스 2는 $$N=8$$ 을 만족한다.
테스트 케이스 3-5는 $N\le 50$ 을 만족한다.
테스트 케이스 6-8은 $N\le 500$ 을 만족한다.
테스트 케이스 9-12는 $N\le 3000$ 을 만족한다.
테스트 케이스 13-16은 추가 제약이 없다.

문제 제공: Benjamin Qi

입력 형식

첫째 줄에 $$N$$ 과 $$M$$ 이 주어진다.

출력 형식

정수 하나를 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 exercise.in · 출력을 쓸 파일 exercise.out

예제 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}$ .

Note: This problem has an expanded memory limit of 512 MB.

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2019-2020 > US Open > Platinum

올림피아드 > USACO > 2019-2020 > US Open > Platinum

태그

JudgeUSACO

운동

평가 및 의견

풀이 제출