#line 1 "modint_dynamic.test.cpp" #define PROBLEM = "https://yukicoder.me/problems/no/1092" // 提出時にassertはオフ #ifndef DEBUG #ifndef NDEBUG #define NDEBUG #endif #endif #include #line 2 "/home/cocojapanpan/Procon_CPP/proconLibrary/myLibrary/modint_dynamic.hpp" #line 2 "/home/cocojapanpan/Procon_CPP/proconLibrary/myLibrary/innermath_modint.hpp" #line 4 "/home/cocojapanpan/Procon_CPP/proconLibrary/myLibrary/innermath_modint.hpp" #ifdef _MSC_VER #include #endif namespace innermath_modint{ using ll = long long; using ull = unsigned long long; using u128 = __uint128_t; // xのmodを[0, mod)で返す constexpr ll safe_mod(ll x, ll mod) { x %= mod; if (x < 0) x += mod; return x; } constexpr ll pow_mod_constexpr(ll x, ll n, ll mod) { if (mod == 1) return 0; ll ret = 1; ll beki = safe_mod(x, mod); while (n) { // LSBから順に見る if (n & 1) { ret = (ret * beki) % mod; } beki = (beki * beki) % mod; n >>= 1; } return ret; } // int型(2^32以下)の高速な素数判定 constexpr bool is_prime_constexpr(int n) { if (n <= 1) return false; if (n == 2 || n == 7 || n == 61) return true; if (n % 2 == 0) return false; // ミラーラビン判定 int型ならa={2,7,61}で十分 constexpr ll bases[] = {2, 7, 61}; // n-1 = 2^r * d ll d = n - 1; while (d % 2 == 0) d >>= 1; // 素数modは1の平方根として非自明な解を持たない // つまり非自明な解がある→合成数 for (ll a : bases) { ll t = d; ll y = pow_mod_constexpr(a, t, n); // yが1またはn-1になれば抜ける while (t != n - 1 && y != 1 && y != n - 1) { y = (y * y) % n; t <<= 1; } // 1の平方根として1と-1以外の解(非自明な解)が存在 if (y != n - 1 && t % 2 == 0) { return false; } } return true; } // 拡張ユークリッドの互除法 g = gcd(a,b)と、ax = g (mod b)なる0 <= x < // b/gのペアを返す constexpr std::pair inv_gcd(ll a, ll b) { a = safe_mod(a, b); // aがbの倍数 if (a == 0) return {b, 0}; // 以下 0 <= a < b // [1] s - m0 * a = 0 (mod b) // [2] t - m1 * a = 0 (mod b) // [3] s * |m1| + t * |m0| <= b ll s = b, t = a; ll m0 = 0, m1 = 1; while (t) { // s → s mod t // m0 → m0 - m1 * (s / t) ll u = s / t; s -= t * u; m0 -= m1 * u; std::swap(s, t); std::swap(m0, m1); } // s = gcd(a, b) // 終了の直前のステップにおいて // [1] k * s - m0 * a = 0 (mod b) // [2] s - m1 * a = 0 (mod b) // [3] (k * s) * |m1| + s * |m0| <= b // |m0| < b / s if (m0 < 0) m0 += b / s; return {s, m0}; } // barret reduction 掛け算のmodの定数倍高速化(modが定数でない場合に使用) struct barretReduction { public: explicit barretReduction(uint _mod) : mod(_mod), imod((ull)(-1) / mod + 1) {} // unsignedの場合、負で巡回する uint get_mod() const { return mod; } uint mul(int a, int b) const { ull z = a; z *= b; #ifdef _MSC_VER ull x; _umul128(z, imod, &x) #else // x = z / mod またはその +1 // 割り算をビットシフトにすることで高速化 ull x = (ull)(((u128)z * imod) >> 64); #endif // z - x * mod = z % mod - mod の場合、uintなので 2^32 - (mod - // z % mod) つまりmodを足せば 2^32 + z % // modとなり、求めるmodになる uint v = (uint)(z - x * mod); if (v >= mod) v += mod; return v; } private: uint mod; ull imod; // ceil(2^64 / mod) }; } #line 5 "/home/cocojapanpan/Procon_CPP/proconLibrary/myLibrary/modint_dynamic.hpp" struct modint_dynamic { using ll = long long; private: ll value; static innermath_modint::barretReduction &get_bt() { static innermath_modint::barretReduction bt(1); return bt; } public: modint_dynamic(ll x = 0) noexcept : value(x % get_mod()) { if(value < 0) value += get_mod(); } static void set_mod(int mod) noexcept { assert(1 <= mod); get_bt() = innermath_modint::barretReduction((uint)mod); } static int get_mod() noexcept { return (int)(get_bt().get_mod()); } ll val() const noexcept { return value; } modint_dynamic operator-() const noexcept { return modint_dynamic(-value); } modint_dynamic& operator++() noexcept { ++value; if(value == get_mod()) value = 0; return *this; } modint_dynamic& operator--() noexcept { if(value == 0) value = get_mod(); --value; return *this; } modint_dynamic operator++(int) noexcept { modint_dynamic cpy(*this); ++(*this); return cpy; } modint_dynamic operator--(int) noexcept { modint_dynamic cpy(*this); --(*this); return cpy; } modint_dynamic& operator+=(const modint_dynamic &rhs) noexcept { value += rhs.value; if(value >= get_mod()) value -= get_mod(); return *this; } modint_dynamic& operator-=(const modint_dynamic &rhs) noexcept { value += (get_mod() - rhs.value); if(value >= get_mod()) value -= get_mod(); return *this; } modint_dynamic& operator*=(const modint_dynamic &rhs) noexcept { // barret reduction でコンパイラの代わりに定数倍高速化 value = get_bt().mul(value, rhs.value); return *this; } modint_dynamic operator+(const modint_dynamic &rhs) const noexcept { modint_dynamic cpy(*this); return cpy += rhs; } modint_dynamic operator-(const modint_dynamic &rhs) const noexcept { modint_dynamic cpy(*this); return cpy -= rhs; } modint_dynamic operator*(const modint_dynamic &rhs) const noexcept { modint_dynamic cpy(*this); return cpy *= rhs; } modint_dynamic pow(ll beki) { modint_dynamic curbekimod(*this); modint_dynamic ret(1); while(beki > 0) { if(beki & 1) ret *= curbekimod; curbekimod *= curbekimod; beki >>= 1; } return ret; } // valueの逆元を求める modint_dynamic inv() const noexcept { // 拡張ユークリッドの互除法 auto [gcd_value_mod, inv_value] = innermath_modint::inv_gcd(value, get_mod()); assert(gcd_value_mod == 1); return modint_dynamic(inv_value); } modint_dynamic& operator/=(const modint_dynamic &rhs) noexcept { return (*this) *= rhs.inv(); } modint_dynamic operator/(const modint_dynamic &rhs) const noexcept { modint_dynamic cpy(*this); return cpy /= rhs; } }; #line 11 "modint_dynamic.test.cpp" using namespace std; using ll = long long; #define ALL(x) (x).begin(), (x).end() template using vec = vector; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int P, N; cin >> P >> N; vec A(N); for(int &a : A) cin >> a; string S; cin >> S; modint_dynamic::set_mod(P); // cout << modint_dynamic::get_mod() << "\n"; modint_dynamic ans(A[0]); cout << ans.val() << "\n"; for(int i = 1; i < N; i++){ if(S[i - 1] == '+') { ans += A[i]; } else if(S[i - 1] == '-') { ans -= A[i]; } else if(S[i - 1] == '*') { ans *= A[i]; } else { ans /= A[i]; } cout << ans.val() << "\n"; } }