취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 25823번 문제인 조합의 합의 합이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/25823 

$n$의 값이 고정되어 있을 때, 다음 식이 성립한다:
$\sum _n^{k=0}{(\genfrac{}{}{0ex}{}{n}{k})}^2=(\genfrac{}{}{0ex}{}{2n}{n})$

$n$행 $n$열의 칸을 가진 격자의 좌하단 칸에서 우상단 칸까지 가는 최단경로의 경우의 수(우변)은 좌상단 칸과 우하단 칸을 잇는 대각선 위의 각 칸을 지나는 경우의 수의 합(좌변)과 같다는 점을 관찰하면 위 식이 자명함을 알 수 있을 것이다.

따라서 3 이상 $M$ 이하의 각 정수 $m$에 대하여 $(\genfrac{}{}{0ex}{}{2m}{m})$의 값을 빠르게 구해 문제를 해결하자. 이를 구하는 방법은 다양하므로, 자신이 익숙한 방법을 사용하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

int fact[400001];
int invfact[400001];

void finit() {
	fact[0] = 1;
	for (int i = 1; i < 400001; i++) {
		fact[i] = (ll)fact[i - 1] * i % 1000000007;
	}
	invfact[0] = invfact[1] = 1;
	for (int i = 2; i < 400001; i++) {
		invfact[i] = 1000000007 - (ll)(1000000007 / i) * invfact[1000000007 % i] % 1000000007;
	}
	for (int i = 1; i < 400001; i++) invfact[i] = (ll)invfact[i - 1] * invfact[i] % 1000000007;
}

int comb(int N, int R) {
	return (ll)fact[N] * (((ll)invfact[R] * invfact[N - R]) % 1000000007) % 1000000007;
}

int M;
int ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	finit();

	cin >> M;
	for (int m = 3; m <= M; m++) {
		ans += comb((m) * 2, m);
		if (ans > 1000000006) ans -= 1000000007;
	}

	cout << ans;
}