結果

問題 No.1092 modular arithmetic
ユーザー yano2xy
提出日時 2023-12-30 14:38:26
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 59 ms / 2,000 ms
コード長 4,538 bytes
コンパイル時間 2,159 ms
コンパイル使用メモリ 196,196 KB
最終ジャッジ日時 2025-02-18 15:37:35
ジャッジサーバーID
（参考情報） 		judge1 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0