10.30.2011

Powers, Factorials, Permutations and Combinations in C++

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_;
};

0 件のコメント:

コメントを投稿