# [Gold II] 최대 사이클 1 [문제 링크](https://www.acmicpc.net/problem/2682) ## 문제 설명 <p> P는 1부터 n까지 수로 이루어진 순열이다. 최대 사이클 1은 P(1), P(P(1)), P(P(P(1))), ... 중 최댓값이다.</p> <p> 예를 들어 수열 P가 (3, 2, 5, 4, 1, 7, 8, 6) 이라면</p> <p> P(1) = 3</p> <p> P(P(1)) = P(3) = 5</p> <p> P(P(P(1))) = P(5) = 1</p> <p> 따라서 3, 5, 1이 반복되며, 최댓값은 5가 된다.</p> <p> 정수 n(n > 0)과 k(1 <= k <= n)이 주어졌을 때, 최대 사이클 1의 값이 k인 순열의 개수를 구하시오.</p> ## 입력 <p> 첫째 줄에 테스트 케이스의 개수 T(1 <= T <= 1,000)가 주어진다. 각 테스트 케이스는 두 개의 정수 n과 k로 이루어져 있다. (1 <= k <= n <= 20)</p> ## 출력 <p> 각 테스트 케이스에 대해서 1, ... n으로 이루어진 순열 중에 최대 사이클 1의 값이 k인 순열의 개수를 출력한다.</p> ## 풀이 #### 순열 사이클에 속하는 조합을 선택하고, 그 그룹과 나머지 그룹을 순열로 배치해서 경우의 수를 찾으면 된다. #### fact[k-2]/fact[i-2]/fact[k-i] : 1과 k를 제외한 2~k-1중 i-2개를 선택하는 경우의 수 #### fact[i-1] : 선택한 조합을 순열 사이클로 나타낼 수 있는 경우의 수 (1을 고정시키고 나머지는 랜덤) #### fact[n-i] : 순열 사이클을 제외한 나머지 수들을 배치하는 경우의 수 ``` c++ #include<bits/stdc++.h> using namespace std; long long fact[21] = {1, }; int main() { ios::sync_with_stdio(0); cin.tie(0); for(int i=1;i<=20;i++) fact[i] = fact[i-1]*i; int t; cin >> t; while(t--) { int n, k; cin >> n >> k; if(k==1) { cout << fact[n-1] << '\n'; } else { long long sum=0; for(int i=2;i<=k;i++) { sum += (fact[k-2]/fact[i-2]/fact[k-i]) * fact[i-1] * fact[n-i]; } cout << sum << '\n'; } } } ```