結果

問題 No.16 累乗の加算
コンテスト
ユーザー hly1204
提出日時 2020-09-07 23:56:45
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 3,932 bytes
コンパイル時間 1,051 ms
コンパイル使用メモリ 113,160 KB
最終ジャッジ日時 2025-01-14 08:19:27
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifndef LOCAL
#define NDEBUG
#endif
#include <algorithm>
#include <cassert>
#include <cstring>
#include <functional>
#include <initializer_list>
#include <iostream>
#include <memory>
#include <random>
#include <vector>

template <std::uint32_t P> struct MontgomeryModInt32 {
public:
  using i32 = std::int32_t;
  using u32 = std::uint32_t;
  using i64 = std::int64_t;
  using u64 = std::uint64_t;
  using mont = MontgomeryModInt32;

private:
  u32 v;

  static constexpr u32 get_r() {
    u32 iv = P;
    for (u32 i = 0; i != 4; ++i) iv *= 2U - P * iv;
    return -iv;
  }

  static constexpr u32 r = get_r(), r2 = -u64(P) % P;

  static_assert((P & 1) == 1);
  static_assert(-r * P == 1);
  static_assert(P < (1 << 30));

  static constexpr u32 pow_mod(u32 x, u64 y) {
    u32 res = 1;
    for (; y != 0; y >>= 1, x = u64(x) * x % P)
      if (y & 1) res = u64(res) * x % P;
    return res;
  }

public:
  static constexpr u32 get_pr() {
    u32 tmp[32] = {}, cnt = 0;
    const u64 phi = P - 1;
    u64 m = phi;
    for (u64 i = 2; i * i <= m; ++i)
      if (m % i == 0) {
        tmp[cnt++] = i;
        while (m % i == 0) m /= i;
      }
    if (m != 1) tmp[cnt++] = m;
    for (u64 res = 2; res != P; ++res) {
      bool flag = true;
      for (u32 i = 0; i != cnt && flag; ++i) flag &= pow_mod(res, phi / tmp[i]) != 1;
      if (flag) return res;
    }
    return 0;
  }

  MontgomeryModInt32() = default;
  ~MontgomeryModInt32() = default;
  constexpr MontgomeryModInt32(u32 v) : v(reduce(u64(v) * r2)) {}
  constexpr MontgomeryModInt32(const mont &rhs) : v(rhs.v) {}
  static constexpr u32 reduce(u64 x) { return x + (u64(u32(x) * r) * P) >> 32; }
  static constexpr u32 norm(u32 x) { return x - (P & -(x >= P)); }
  constexpr u32 get() const {
    u32 res = reduce(v) - P;
    return res + (P & -(res >> 31));
  }
  explicit constexpr operator u32() const { return get(); }
  explicit constexpr operator i32() const { return i32(get()); }
  constexpr mont &operator=(const mont &rhs) { return v = rhs.v, *this; }
  constexpr mont operator-() const {
    mont res;
    return res.v = (P << 1 & -(v != 0)) - v, res;
  }
  constexpr mont inv() const { return pow(-1); }
  constexpr mont &operator+=(const mont &rhs) {
    return v += rhs.v - (P << 1), v += P << 1 & -(v >> 31), *this;
  }
  constexpr mont &operator-=(const mont &rhs) {
    return v -= rhs.v, v += P << 1 & -(v >> 31), *this;
  }
  constexpr mont &operator*=(const mont &rhs) { return v = reduce(u64(v) * rhs.v), *this; }
  constexpr mont &operator/=(const mont &rhs) { return this->operator*=(rhs.inv()); }
  friend mont operator+(const mont &lhs, const mont &rhs) { return mont(lhs) += rhs; }
  friend mont operator-(const mont &lhs, const mont &rhs) { return mont(lhs) -= rhs; }
  friend mont operator*(const mont &lhs, const mont &rhs) { return mont(lhs) *= rhs; }
  friend mont operator/(const mont &lhs, const mont &rhs) { return mont(lhs) /= rhs; }
  friend bool operator==(const mont &lhs, const mont &rhs) { return norm(lhs.v) == norm(rhs.v); }
  friend bool operator!=(const mont &lhs, const mont &rhs) { return norm(lhs.v) != norm(rhs.v); }
  friend std::istream &operator>>(std::istream &is, mont &rhs) {
    return is >> rhs.v, rhs.v = reduce(u64(rhs.v) * r2), is;
  }
  friend std::ostream &operator<<(std::ostream &os, const mont &rhs) { return os << rhs.get(); }
  constexpr mont pow(i64 y) const {
    if ((y %= P - 1) < 0) y += P - 1; // phi(P) = P - 1, assume P is a prime number
    mont res(1), x(*this);
    for (; y != 0; y >>= 1, x *= x)
      if (y & 1) res *= x;
    return res;
  }
};

int main() {
#ifdef LOCAL
  std::freopen("..\\in", "r", stdin), std::freopen("..\\out", "w", stdout);
#endif
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  int n, m;
  std::cin >> n >> m;
  MontgomeryModInt32<1000003> a(n), ans(0);
  while (m--) {
    int v;
    std::cin >> v;
    ans += a.pow(v);
  }
  std::cout << ans;
  return 0;
}
0