C++: 累乗、階乗、順列、組み合わせ
これらの計算結果に対するM（通常は10^9付近）の剰余をメモリ上へ格納するクラス。
メモリ使用量が64MB程度以内に収まるよう入力値を制限しているが、取得に関してはチェックしない。
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_;
};
