「二項係数 mod 素数」を verify する問題
問題概要
素数 が与えられる。整数 の組が 組与えられるので、それぞれについて を で割ったあまりを求めよ。
制約
解法
ここで書いた方法を実装することで AC できる。ただし、modint
は自前のものを用意することとした。
コード
#include <bits/stdc++.h> using namespace std; // modint struct Fp { // static menber static int MOD; // inner value long long val; // constructor Fp() : val(0) { } Fp(long long v) : val(v % MOD) { if (val < 0) val += MOD; } long long get() const { return val; } static int get_mod() { return MOD; } static void set_mod(int mod) { MOD = mod; } // arithmetic operators Fp operator - () const { return val ? MOD - val : 0; } Fp operator + (const Fp &r) const { return Fp(*this) += r; } Fp operator - (const Fp &r) const { return Fp(*this) -= r; } Fp operator * (const Fp &r) const { return Fp(*this) *= r; } Fp operator / (const Fp &r) const { return Fp(*this) /= r; } Fp& operator += (const Fp &r) { val += r.val; if (val >= MOD) val -= MOD; return *this; } Fp& operator -= (const Fp &r) { val -= r.val; if (val < 0) val += MOD; return *this; } Fp& operator *= (const Fp &r) { val = val * r.val % MOD; return *this; } Fp& operator /= (const Fp &r) { long long a = r.val, b = MOD, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b, swap(a, b); u -= t * v, swap(u, v); } val = val * u % MOD; if (val < 0) val += MOD; return *this; } Fp pow(long long n) const { Fp res(1), mul(*this); while (n > 0) { if (n & 1) res *= mul; mul *= mul; n >>= 1; } return res; } Fp inv() const { Fp res(1), div(*this); return res / div; } // other operators bool operator == (const Fp &r) const { return this->val == r.val; } bool operator != (const Fp &r) const { return this->val != r.val; } friend istream& operator >> (istream &is, Fp &x) { is >> x.val; x.val %= x.get_mod(); if (x.val < 0) x.val += x.get_mod(); return is; } friend ostream& operator << (ostream &os, const Fp &x) { return os << x.val; } friend Fp modpow(const Fp &r, long long n) { return r.pow(n); } friend Fp modinv(const Fp &r) { return r.inv(); } }; int Fp::MOD; // Binomial coefficient template<class T> struct BiCoef { vector<T> fact_, inv_, finv_; constexpr BiCoef() {} constexpr BiCoef(int n) : fact_(n, 1), inv_(n, 1), finv_(n, 1) { init(n); } constexpr void init(int n) { fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1); int MOD = fact_[0].get_mod(); for(int i = 2; i < n; i++){ fact_[i] = fact_[i-1] * i; inv_[i] = -inv_[MOD%i] * (MOD/i); finv_[i] = finv_[i-1] * inv_[i]; } } constexpr T com(int n, int k) const noexcept { if (n < k || n < 0 || k < 0) return 0; return fact_[n] * finv_[k] * finv_[n-k]; } constexpr T fact(int n) const noexcept { if (n < 0) return 0; return fact_[n]; } constexpr T inv(int n) const noexcept { if (n < 0) return 0; return inv_[n]; } constexpr T finv(int n) const noexcept { if (n < 0) return 0; return finv_[n]; } }; const int MAX = 11000000; int main() { int T, M; cin >> T >> M; using mint = Fp; mint::set_mod(M); BiCoef<mint> bc(MAX); while (T--) { int n, k; cin >> n >> k; cout << bc.com(n, k) << endl; } }