Submission #4794708


Source Code Expand

Copy
#include <cstdint>

template <std::uint_fast64_t Modulus> class modint {
  using u64 = std::uint_fast64_t;

public:
  u64 a;

  constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {}
  constexpr u64 &value() noexcept { return a; }
  constexpr const u64 &value() const noexcept { return a; }
  constexpr modint operator+(const modint rhs) const noexcept {
    return modint(*this) += rhs;
  }
  constexpr modint operator-(const modint rhs) const noexcept {
    return modint(*this) -= rhs;
  }
  constexpr modint operator*(const modint rhs) const noexcept {
    return modint(*this) *= rhs;
  }
  constexpr modint operator/(const modint rhs) const noexcept {
    return modint(*this) /= rhs;
  }
  constexpr modint &operator+=(const modint rhs) noexcept {
    a += rhs.a;
    if (a >= Modulus) {
      a -= Modulus;
    }
    return *this;
  }
  constexpr modint &operator-=(const modint rhs) noexcept {
    if (a < rhs.a) {
      a += Modulus;
    }
    a -= rhs.a;
    return *this;
  }
  constexpr modint &operator*=(const modint rhs) noexcept {
    a = a * rhs.a % Modulus;
    return *this;
  }
  constexpr modint &operator/=(modint rhs) noexcept {
    u64 exp = Modulus - 2;
    while (exp) {
      if (exp % 2) {
        *this *= rhs;
      }
      rhs *= rhs;
      exp /= 2;
    }
    return *this;
  }
};

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  using mint = modint<1000000007>;

  int n, x;
  std::cin >> n >> x;
  std::vector<int> s(n);
  for (auto &e : s) {
    std::cin >> e;
  }
  std::sort(s.begin(), s.end());

  std::vector<std::vector<mint>> dp(n + 1, std::vector<mint>(x + 1));

  for (int i = 0; i <= x; ++i) {
    dp[0][i] = i;
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= x; ++j) {
      dp[i + 1][j] = dp[i][j] * i + dp[i][j % s[i]];
    }
  }

  std::cout << dp[n][x].value() << std::endl;

  return 0;
}

Submission Info

Submission Time
Task D - Modulo Operations
User noshi91
Language C++14 (GCC 5.4.1)
Score 600
Code Size 1972 Byte
Status AC
Exec Time 178 ms
Memory 158592 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 25
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 11 ms 9600 KB
test_01.txt AC 1 ms 256 KB
test_02.txt AC 1 ms 256 KB
test_03.txt AC 178 ms 158592 KB
test_04.txt AC 178 ms 158592 KB
test_05.txt AC 135 ms 119808 KB
test_06.txt AC 155 ms 137600 KB
test_07.txt AC 99 ms 87552 KB
test_08.txt AC 101 ms 89088 KB
test_09.txt AC 108 ms 88320 KB
test_10.txt AC 119 ms 106112 KB
test_11.txt AC 151 ms 134400 KB
test_12.txt AC 153 ms 135936 KB
test_13.txt AC 116 ms 103680 KB
test_14.txt AC 60 ms 52736 KB
test_15.txt AC 64 ms 55552 KB
test_16.txt AC 26 ms 21888 KB
test_17.txt AC 35 ms 29184 KB
test_18.txt AC 9 ms 7040 KB
test_19.txt AC 104 ms 92288 KB
test_20.txt AC 36 ms 31616 KB
test_21.txt AC 65 ms 56960 KB
test_22.txt AC 10 ms 8704 KB