Submission #2042287

---

Source Code Expand

#define _CRT_SECURE_NO_WARNINGS
#include <array>
#include <cstdio>

using namespace std;

const int INF = 1000000007;

const int MAX_N = 100;
const int MAX_K = 500;

array<int, MAX_N + MAX_K> FCT;
array<int, MAX_N + MAX_K> INV;

int modmulti(int a, int b)
{
    int res = 0;
    int mod = a % INF;
    while (b > 0)
    {
        if ((b & 1) == 1)
        {
            res += mod;
            if (res > INF)
            {
                res -= INF;
            }
        }
        mod <<= 1;
        if (mod > INF)
        {
            mod -= INF;
        }
        b >>= 1;
    }
    return res;
}

int modcalc(int a, int b)
{
    // O(log b)
    int d = 0;
    if (b == 0)
    {
        return 1;
    }
    else if ((b & 1) == 0)
    {
        // 偶数 bを半分にできる
        d = modcalc(a, b / 2);
        return modmulti(d, d);
    }
    else
    {
        // 奇数 -1乗から1乗をかける
        return modmulti(a, modcalc(a, b - 1));
    }
}

int combination(int a, int b)
{
    // tmp = a! / b!
    int tmp = modmulti(FCT[a], INV[b]);
    // tmp / (a - b)!
    return modmulti(tmp, INV[a - b]);
}

void factorial(int x)
{
    FCT[0] = 1;
    FCT[1] = 1;
    for (int i = 2; i <= x; i++)
    {
        FCT[i] = modmulti(FCT[i - 1], i);
    }
}

void inverse(int x)
{
    INV[0] = 1;
    INV[1] = 1;
    INV[x] = modcalc(FCT[x], INF - 2);
    for (int i = x - 1; 2 <= i; i--)
    {
        INV[i] = modmulti(INV[i + 1], i + 1);
    }
}

int main()
{
    int N, K;

    if (scanf("%d%d", &N, &K) < 2) return 0;

    // 階乗テーブル作成
    factorial(N + K - 1);

    // 逆元テーブル作成
    inverse(N + K - 1);

    int ans;
    if (K < N)
    {
        // 「N 種類のものから重複を許して K 個選ぶ」方法と
        // 「K 個の ○ と N-1 個の ｜(仕切り)を 1 列に並べる」方法は
        // 1 対 1 に対応する
        // nHk = (n+k-1)Ck

        // (n+k-1)Ck
        ans = combination(N + K - 1, K);
    }
    else
    {
        // nCk%n
        ans = combination(N, K % N);
    }

    printf("%d\n", ans);
    return 0;
}

Submission Info

Judge Result