[BOJ] 13430 합 구하기

문제 링크

www.acmicpc.net/problem/13430

풀이

$S$는 다음과 같다.

$$ \begin{aligned} S(0, n) &= n\\ S(1, n) &= \sum_{i=1}^{n} i\\ &= \frac{n(n+1)}{2} \\ S(2, n) &= \sum_{i=1}^{n} \frac{i(i+1)}{2}\\ &= \frac{n(n+1)(n+2)}{6}\\ S(3, n) &= \sum_{i=1}^{n} \frac{i(i+1)(i+2)}{6}\\ &= \frac{n(n+1)(n+2)(n+3)}{24}\\ \end{aligned} $$

$S(k, n) = \frac{n(n+1)(n+2)\cdots(n+k)}{(k+1)!}$이라는 규칙은 보이는데, 실제로 성립하는 것을 보이려면 어떻게 해야 할까?
이는 귀납법을 통해 보일 수 있다.

1. $k = 0$일 때, $S(0, n) = \frac{n}{(0+1)!} = n$으로 성립한다.
2. $t > 0$인 $t$에 대해서, $S(t, n) = \frac{i(i+1)(i+2)\cdots(i+t)}{(t+1)!}$ 이라고 가정하자. 그러면 $S(t+1, n)$은
   $$ \begin{aligned} S(t+1, n) &= \sum_{i=1}^{n} S(t, i)\\ &= \sum_{i=1}^{n} \frac{i(i+1)(i+2)\cdots(i+t)}{(t+1)!}\\ &= \sum_{i=1}^{n} \frac{(t+2)i(i+1)(i+2)\cdots(i+t)}{(t+2)!}\\ &= \sum_{i=1}^{n} \frac{i(i+1)(i+2)\cdots(i+t+1) - (i-1)i(i+1)\cdots(i+t)}{(t+2)!}\\ &= \frac{n(n+1)(n+2)\cdots(n+t+1)}{(t+2)!} \end{aligned} $$
   따라서, $S(k, n) = \frac{n(n+1)(n+2)\cdots(n+k)}{(k+1)!}$임이 성립한다.

$k$는 최대 50이므로 분자와 분모는 쉽게 구할 수 있다.
하지만 문제에서는 $10^9+7$로 나눈 나머지를 구해야 하는데, 합동식에서 $x$로 나누는 연산은 법 $10^9+7$에 대해 $x$의 곱셈의 역원을 곱하는 것과 같다. 곱셈의 역원은 페르마의 소정리를 이용하여 구하면 된다.

C++ 코드

#include <bits/stdc++.h>
#define X first
#define Y second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define ini(x, y) memset(x, y, sizeof(x))
#define endl '\n'
#define fastio cin.sync_with_stdio(false); cin.tie(nullptr)
using namespace std;

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
const int MOD = 1e9 + 7;
const int dx[] = { -1, 0, 1, 0, -1, 1, 1, -1 };
const int dy[] = { 0, 1, 0, -1, 1, 1, -1, -1 };

ll f(ll n, ll r) {
    ll ret = 1;
    while (r) {
        if (r & 1) ret = ret * n % MOD;
        n = n * n % MOD;
        r >>= 1;
    }
    return ret;
}
int main() {
    fastio;
    int k, n;
    cin >> k >> n;

    ll a = 1, b = 1;
    for (int i = 0; i < k + 1; ++i) {
        a = a * (k + n - i) % MOD;
        b = b * (k + 1 - i) % MOD;
    }

    cout << a * f(b, MOD - 2) % MOD;

    return 0;
}

Java 코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static final long MOD = 1_000_000_007;

    static long f(long n, long r) {
        long ret = 1;
        for (; r > 0; r >>= 1) {
            if (r % 2 > 0) ret = ret * n % MOD;
            n = n * n % MOD;
        }
        return ret;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());

        int k = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());

        long a = 1, b = 1;
        for (int i = 0; i <= k; ++i) {
            a = a * (n + i) % MOD;
            b = b * (i + 1) % MOD;
        }

        System.out.println(a * f(b, MOD - 2) % MOD);
    }
}