結果
問題 | No.1092 modular arithmetic |
ユーザー | yano2xy |
提出日時 | 2023-12-30 14:38:26 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 56 ms / 2,000 ms |
コード長 | 4,538 bytes |
コンパイル時間 | 2,603 ms |
コンパイル使用メモリ | 204,504 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-27 16:41:24 |
合計ジャッジ時間 | 6,219 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 47 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 47 ms
6,940 KB |
testcase_04 | AC | 40 ms
6,940 KB |
testcase_05 | AC | 40 ms
6,940 KB |
testcase_06 | AC | 29 ms
6,940 KB |
testcase_07 | AC | 40 ms
6,940 KB |
testcase_08 | AC | 45 ms
6,940 KB |
testcase_09 | AC | 39 ms
6,940 KB |
testcase_10 | AC | 33 ms
6,944 KB |
testcase_11 | AC | 36 ms
6,944 KB |
testcase_12 | AC | 29 ms
6,940 KB |
testcase_13 | AC | 16 ms
6,940 KB |
testcase_14 | AC | 18 ms
6,944 KB |
testcase_15 | AC | 5 ms
6,944 KB |
testcase_16 | AC | 14 ms
6,944 KB |
testcase_17 | AC | 19 ms
6,940 KB |
testcase_18 | AC | 47 ms
6,944 KB |
testcase_19 | AC | 29 ms
6,944 KB |
testcase_20 | AC | 49 ms
6,940 KB |
testcase_21 | AC | 38 ms
6,944 KB |
testcase_22 | AC | 46 ms
6,944 KB |
testcase_23 | AC | 47 ms
6,944 KB |
testcase_24 | AC | 16 ms
6,940 KB |
testcase_25 | AC | 36 ms
6,940 KB |
testcase_26 | AC | 47 ms
6,940 KB |
testcase_27 | AC | 9 ms
6,940 KB |
testcase_28 | AC | 37 ms
6,940 KB |
testcase_29 | AC | 56 ms
6,944 KB |
testcase_30 | AC | 38 ms
6,940 KB |
testcase_31 | AC | 6 ms
6,944 KB |
testcase_32 | AC | 33 ms
6,940 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (int i = 0; i < (n); i++) using ll = long long; #ifdef LOCAL #include <util/debug_print.hpp> #else #define debug(...) static_cast<void>(0) #endif #ifndef _LIB_DYNAMIC_MODINT_HPP #define _LIB_DYNAMIC_MODINT_HPP 1 #include <cassert> #include <iostream> struct barrett { unsigned int _m; unsigned long long im; barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {} unsigned int umod() const { return _m; } unsigned int mul(unsigned int a, unsigned int b) const { unsigned long long z = a; z *= b; unsigned long long x = (unsigned long long)(((unsigned __int128)(z)*im) >> 64); unsigned int v = (unsigned int)(z - x * _m); if (_m <= v) v += _m; return v; } }; template <int id> struct dynamic_modint { using mint = dynamic_modint; private: unsigned int _v; static barrett bt; static unsigned int umod() { return bt.umod(); } static std::pair<unsigned int, unsigned int> inv_gcd(unsigned int a, unsigned int b) { if (a == 0) return {b, 0}; unsigned int s = b, t = a, m0 = 0, m1 = 1; while (t) { const unsigned int u = s / t; s -= t * u; m0 -= m1 * u; std::swap(s, t); std::swap(m0, m1); } if (m0 < 0) m0 += b / s; return {s, m0}; } public: static int mod() { return (int)bt.umod(); } static void set_mod(int m) { assert(0 <= m); bt = barrett(m); } static mint raw(int v) { mint x; x._v = v; return x; } dynamic_modint() : _v(0) {} template <class T> dynamic_modint(T v) { if (std::is_signed_v<T>) { long long x = (long long)(v % (long long)(mod())); if (x < 0) x += mod(); _v = (unsigned int)(x); } else { _v = (unsigned int)(v % mod()); } } unsigned int val() const { return _v; } mint& operator++() { return *this += 1; } mint& operator--() { return *this -= 1; } mint operator++(int) { mint res = *this; ++*this; return res; } mint operator--(int) { mint res = *this; --*this; return res; } mint& operator+=(mint rhs) { if (_v >= umod() - rhs._v) _v -= umod(); _v += rhs._v; return *this; } mint& operator-=(mint rhs) { if (_v < rhs._v) _v += umod(); _v -= rhs._v; return *this; } mint& operator*=(mint rhs) { _v = bt.mul(_v, rhs._v); return *this; } mint& operator/=(mint rhs) { return *this = *this * rhs.inv(); } mint operator+() const { return *this; } mint operator-() const { return mint{} - *this; } mint pow(unsigned long long n) const { assert(0 <= n); mint x = *this, r = 1; while (n) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; } mint inv() const { auto eg = inv_gcd(_v, mod()); assert(eg.first == 1); return (int)eg.second; } friend mint operator+(const mint& lhs, const mint& rhs) { return mint(lhs) += rhs; } friend mint operator-(const mint& lhs, const mint& rhs) { return mint(lhs) -= rhs; } friend mint operator*(const mint& lhs, const mint& rhs) { return mint(lhs) *= rhs; } friend mint operator/(const mint& lhs, const mint& rhs) { return mint(lhs) /= rhs; } friend bool operator==(const mint& lhs, const mint& rhs) { return lhs._v == rhs._v; } friend bool operator!=(const mint& lhs, const mint& rhs) { return lhs._v != rhs._v; } }; template <int id> barrett dynamic_modint<id>::bt(998244353); using modint = dynamic_modint<-1>; #endif // _LIB_DYNAMIC_MODINT_HPP /** * @brief dyanamic_modint */ using mint = modint; // using mint = static_modint<11>; ostream& operator<<(ostream& os, const mint& a) { return os << a.val(); } int main() { int P; cin >> P; mint::set_mod(P); debug(mint(8)); debug(mint(5)); debug(mint(5).inv()); int n; cin >> n; vector<int> A(n); rep(i, n) cin >> A[i]; string s; cin >> s; mint ans = A[0]; rep(i, n - 1) { int a = A[i + 1]; if (s[i] == '+') ans += a; if (s[i] == '-') ans -= a; if (s[i] == '*') ans *= a; if (s[i] == '/') ans /= a; debug(ans); } cout << ans << endl; return 0; }