test/math/CombinationMod-binom.test.cpp

View this file on GitHub
Last update: 2023-05-30 04:49:31+09:00
Problem: https://yukicoder.me/problems/no/741

Depends on

CombinationMod - mod上の二項係数・階乗 (lib/30-math/CombinationMod.cpp)

Code

#define PROBLEM "https://yukicoder.me/problems/no/741"

#include <vector>
#include <iostream>
using namespace std;
#include "../../lib/30-math/CombinationMod.cpp"
constexpr long long MOD = 1000'000'007;

int main(void){
    int N; cin >> N;
    CombinationMod<MOD> CM(N+10);
    cout << CM.binom(N+9,9) << endl;
	return 0;
}

#line 1 "test/math/CombinationMod-binom.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/741"

#include <vector>
#include <iostream>
using namespace std;
#line 1 "lib/30-math/CombinationMod.cpp"
/*
 * @title CombinationMod - mod上の二項係数・階乗
 * @docs md/math/CombinationMod.md
 */
template<long long mod> class CombinationMod {
    vector<long long> fac,finv,inv;
public:
    CombinationMod(int N) : fac(N + 1), finv(N + 1), inv(N + 1) {
        fac[0] = fac[1] = finv[0] = finv[1] = inv[1] = 1;
        for (int i = 2; i <= N; ++i) {
            fac[i] = fac[i - 1] * i % mod;
            inv[i] = mod - inv[mod%i] * (mod / i) % mod;
            finv[i] = finv[i - 1] * inv[i] % mod;
        }
    }
    inline long long binom(int n, int k) {
        return ((n < 0 || k < 0 || n < k) ? 0 : fac[n] * (finv[k] * finv[n - k] % mod) % mod);
    }
    inline long long factorial(int n) {
        return fac[n];
    }
};

//verify https://atcoder.jp/contests/abc021/tasks/abc021_d
#line 7 "test/math/CombinationMod-binom.test.cpp"
constexpr long long MOD = 1000'000'007;

int main(void){
    int N; cin >> N;
    CombinationMod<MOD> CM(N+10);
    cout << CM.binom(N+9,9) << endl;
	return 0;
}