Codeforces Round #745 (Div. 2)-A. CQXYM Count Permutations

문제 설명

효수는 길이가 $2n$ 인 순열중에서 특정 순열을 세고 있다.
순열은 $1$ 부터 $n$까지 $n$개의 수를 무작위로 나열한 것을 말한다. 예를들어 $[2, 3, 1, 5, 4]$ 는 순열이다. 하지만 $[1, 2, 2]$ 는 $2$ 가 배열에 2번 나타났기 때문에 순열이 아니다. 그리고 $[1, 3, 4]$ 는 배열의 길이가 $3$ 이지만 $4$ 가 포함되어 있기 때문이다.

길이가 $2n$ 인 순열 $p$는 $p_i < p_{i + 1}$ 를 만족하는 $i$의 개수가 $n$보다 크거나 같을 때 셀수 있다. 예를 들어

• 순열 $[1, 2, 3, 4]$ 는 셀수 있다. 왜냐하면 $p_i < p_{i + 1}$를 만족하는 $i$의 수가 3개고 이 수는 $n = 2$ 보다 크거나 같기 때문이다. $(i = 1, i = 2, i = 3)$
• 순열 $[3, 2, 1, 4]$ 는 셀수 없다. 왜냐하면 $p_i < p_{i + 1}$를 만족하는 $i$의 수가 1개고 이 수는 $n = 2$ 보다 작기 때문이다. $(i = 3)$

효수는 셀수 있는 순열의 개수를 $1000000007 (10^9 + 7)$ 로 나눈 수를 구하고 싶다.

Input
첫번째 줄에는 테스트 케이스의 수 $t (t \ge 1)$이 주어진다.

각 테스트 케이스에는 정수 $n$이 주어진다. $(1 \le n \le 10^5)$

Output
각 테스트 케이스마다 답을 출력한다.

Example
input
4
1
2
9
91234

output
1
12
830455698
890287984

문제 접근

사용한 알고리즘: 수학, 구현
걸린 시간 : 00:04
처음에는 어떻게 푸는지 몰랐지만 $4!$의 값이 $24$인데, 문제의 답이 $12$인것을 보고 설마 2로 나눈 값이 답인가? 라는 생각을 처음 했고, $18!$의 값을 2로 나눈 수가 답인 것을 보고 확신해서 금방 푼 문제이다. 때로는 이런 직관이 A번 문제에서는 잘 먹힌다는 것을 깨달은 문제이다. 왜인지는 수식이 이해가 안되서 패스.

정답 코드

#include <iostream>
using namespace std;

const int DIV = 1000000007;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        long long res = 1LL;
        for(long long i = 1; i <= 2 * n; i++){
            if(i == 2) continue;
            res = (res * i * 1LL) % DIV;
        }
        cout << res % DIV << "\n";
    }
    return 0;
}