# [Silver III] 프랙탈 수열 [문제 링크](https://www.acmicpc.net/problem/31499) ## 문제 설명 <p>$N$개의 서로 다른 양의 정수로 구성된 수열 $A$가 있다. 이 수열을 오름차순으로 정렬한 수열을 $B$라 하자. 그리고 $B$에 의해 결정되는 길이 $N$의 수열 $C$를 다음과 같이 정의한다.</p> <p>$$c_i = \begin{cases} b_{b_i}, & \text{if } 1 \le b_i \le N \\ 0, & \text{otherwise} \end{cases}$$</p> <p>여기서 $1 \le i \le N$인 모든 $i$에 대해, $b_i$는 $B$의 $i$번째 원소를, $c_i$는 $C$의 $i$번째 원소를 나타낸다.</p> <p>이때, $B = C$가 되도록 하는 수열 $A$를 <strong>프랙탈 수열</strong>이라고 하자. $N$과 $M$이 주어졌을 때, 길이가 $N$인 서로 다른 프랙탈 수열의 개수를 $M$으로 나눈 나머지를 구해보자.</p> ## 입력 <p>첫 번째 줄에 두 정수 $N(1 \le N \le 10^3)$과 $M(1 \le M \le 10^9)$이 공백으로 구분되어 주어진다.</p> ## 출력 <p>길이가 $N$인 서로 다른 프랙탈 수열의 개수를 $M$으로 나눈 나머지를 출력한다.</p> ## 풀이 조건을 만족하는 수열은 1부터 N까지 모두 1번씩 나오는 수열이다. 이 수열을 재배치하는 경우는 N!개이기 때문에 N! % m을 출력하면 된다. ``` c++ #include<bits/stdc++.h> using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(0); cin.tie(0); ll n, m; cin >> n >> m; ll ret=1; for(int i=1;i<=n;i++) ret = ret*i%m; cout << ret; } ```