C++: 累乗、階乗、順列、組み合わせ
これらの計算結果に対するM（通常は10^9付近）の剰余をメモリ上へ格納するクラス。
メモリ使用量が64MB程度以内に収まるよう入力値を制限しているが、取得に関してはチェックしない。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | class Power { public: Power(int num, int modulus=1000000007) { if (num > 10000000) { throw std::exception(); } data_.resize(num + 1); data_[0] = 1; for (int i = 1; i <= num; ++i) { data_[i] = ((long long)num * data_[i - 1]) % modulus; } } int operator()(int n) { return data_[n]; } private: std::vector<int> data_;};class Factorial { public: Factorial(int num, int modulus=1000000007) { if (num > 10000000) { throw std::exception(); } data_.resize(num + 1); data_[0] = 1; for (long long i = 1; i <= (long long)num; ++i) { data_[i] = (i * data_[i - 1]) % modulus; } } int operator()(int n) { return data_[n]; } private: std::vector<int> data_;};class Permutation { public: Permutation(int num, int modulus=1000000007) { if (num > 4000) { throw std::exception(); } data_.resize(num + 1); for (int i = 1; i <= num; ++i) { data_[i].resize(num + 1); data_[i][0] = 1; for (int j = 1; j <= i; ++j) { data_[i][j] = ((long long)(i - j + 1) * data_[i][j - 1]) % modulus; } } } int operator()(int n, int r) { return data_[n][r]; } private: std::vector<std::vector<int> > data_;};class Combination { public: Combination(int num, int modulus=1000000007) { if (num > 4000) { throw std::exception(); } data_.resize(num + 1); for (int i = 0; i <= num; ++i) { data_[i].resize(num + 1); data_[i][0] = 1; for (int j = 1; j <= i; ++j) { data_[i][j] = ((long long)data_[i - 1][j] + data_[i - 1][j - 1]) % modulus; } } } int operator()(int n, int r) { return data_[n][r]; } private: std::vector<std::vector<int> > data_;}; |
0 件のコメント:
コメントを投稿