oj.uz

답안 #492789

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
492789 2021-12-08T22:17:38 Z maksim1744 Lucky Numbers (RMI19_lucky) C++17
100 / 100
 81 ms 17716 KB 
/*
    author:  Maksim1744
    created: 09.12.2021 00:29:14
*/

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;

#define mp   make_pair
#define pb   push_back
#define eb   emplace_back

#define sum(a)     ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())

template<typename T>             vector<T>& operator--            (vector<T> &v){for (auto& i : v) --i;            return  v;}
template<typename T>             vector<T>& operator++            (vector<T> &v){for (auto& i : v) ++i;            return  v;}
template<typename T>             istream& operator>>(istream& is,  vector<T> &v){for (auto& i : v) is >> i;        return is;}
template<typename T>             ostream& operator<<(ostream& os,  vector<T>  v){for (auto& i : v) os << i << ' '; return os;}
template<typename T, typename U> pair<T,U>& operator--           (pair<T, U> &p){--p.first; --p.second;            return  p;}
template<typename T, typename U> pair<T,U>& operator++           (pair<T, U> &p){++p.first; ++p.second;            return  p;}
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U> &p){is >> p.first >> p.second;        return is;}
template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U>  p){os << p.first << ' ' << p.second; return os;}
template<typename T, typename U> pair<T,U> operator-(pair<T,U> a, pair<T,U> b){return mp(a.first-b.first, a.second-b.second);}
template<typename T, typename U> pair<T,U> operator+(pair<T,U> a, pair<T,U> b){return mp(a.first+b.first, a.second+b.second);}
template<typename T, typename U> void umin(T& a, U b){if (a > b) a = b;}
template<typename T, typename U> void umax(T& a, U b){if (a < b) a = b;}

#ifdef HOME
#define SHOW_COLORS
#include "/mnt/c/Libs/tools/print.cpp"
#else
#define show(...) void(0)
#define debugf(fun)   fun
#define debugv(var)   var
#define mclock    void(0)
#define shows     void(0)
#define debug  if (false)
#endif

namespace mint_ns {
template<auto P>
struct Modular {
    using value_type = decltype(P);
    value_type value;

    Modular(long long k = 0) : value(norm(k)) {}

    friend Modular<P>& operator += (      Modular<P>& n, const Modular<P>& m) { n.value += m.value; if (n.value >= P) n.value -= P; return n; }
    friend Modular<P>  operator +  (const Modular<P>& n, const Modular<P>& m) { Modular<P> r = n; return r += m; }

    friend Modular<P>& operator -= (      Modular<P>& n, const Modular<P>& m) { n.value -= m.value; if (n.value < 0)  n.value += P; return n; }
    friend Modular<P>  operator -  (const Modular<P>& n, const Modular<P>& m) { Modular<P> r = n; return r -= m; }
    friend Modular<P>  operator -  (const Modular<P>& n)                      { return Modular<P>(-n.value); }

    friend Modular<P>& operator *= (      Modular<P>& n, const Modular<P>& m) { n.value = n.value * 1ll * m.value % P; return n; }
    friend Modular<P>  operator *  (const Modular<P>& n, const Modular<P>& m) { Modular<P> r = n; return r *= m; }

    friend Modular<P>& operator /= (      Modular<P>& n, const Modular<P>& m) { return n *= m.inv(); }
    friend Modular<P>  operator /  (const Modular<P>& n, const Modular<P>& m) { Modular<P> r = n; return r /= m; }

    Modular<P>& operator ++ (   ) { return *this += 1; }
    Modular<P>& operator -- (   ) { return *this -= 1; }
    Modular<P>  operator ++ (int) { Modular<P> r = *this; *this += 1; return r; }
    Modular<P>  operator -- (int) { Modular<P> r = *this; *this -= 1; return r; }

    friend bool operator == (const Modular<P>& n, const Modular<P>& m) { return n.value == m.value; }
    friend bool operator != (const Modular<P>& n, const Modular<P>& m) { return n.value != m.value; }

    explicit    operator       int() const { return value; }
    explicit    operator      bool() const { return value; }
    explicit    operator long long() const { return value; }

    constexpr static value_type mod()      { return     P; }

    value_type norm(long long k) {
        if (!(-P <= k && k < P)) k %= P;
        if (k < 0) k += P;
        return k;
    }

    Modular<P> inv() const {
        value_type a = value, b = P, x = 0, y = 1;
        while (a != 0) { value_type k = b / a; b -= k * a; x -= k * y; swap(a, b); swap(x, y); }
        return Modular<P>(x);
    }
};
template<auto P> Modular<P> pow(Modular<P> m, long long p) {
    Modular<P> r(1);
    while (p) {
        if (p & 1) r *= m;
        m *= m;
        p >>= 1;
    }
    return r;
}

template<auto P> ostream& operator << (ostream& o, const Modular<P>& m) { return o << m.value; }
template<auto P> istream& operator >> (istream& i,       Modular<P>& m) { long long k; i >> k; m.value = m.norm(k); return i; }
template<auto P> string   to_string(const Modular<P>& m) { return to_string(m.value); }

using Mint = Modular<1000000007>;
// using Mint = Modular<998244353>;
// using Mint = long double;

vector<Mint> f, fi;
void init_C(int n) {
    f.assign(n, 1); fi.assign(n, 1);
    for (int i = 2; i < n; ++i) f[i] = f[i - 1] * i;
    fi.back() = Mint(1) / f.back();
    for (int i = n - 2; i >= 0; --i) fi[i] = fi[i + 1] * (i + 1);
}
Mint C(int n, int k) {
    if (k < 0 || k > n) return 0;
    else return f[n] * fi[k] * fi[n - k];
}
}
using namespace mint_ns;

template<typename T, int N>
struct Matrix {
    array<array<T, N>, N> m;

    Matrix() {
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                m[i][j] = 0;
            }
        }
    }
    Matrix(std::initializer_list<std::initializer_list<T>> s) {
        int i = 0;
        for (auto it = s.begin(); it != s.end(); ++it) {
            int j = 0;
            for (auto it2 = it->begin(); it2 != it->end(); ++it2) {
                m[i][j] = *it2;
                ++j;
            }
            ++i;
        }
    }

    static Matrix E() {
        Matrix e;
        for (int i = 0; i < N; ++i) {
            e[i][i] = 1;
        }
        return e;
    }

    array<T, N> &operator[](int i) {
        return m[i];
    }

    const array<T, N> &operator[](int i) const {
        return m[i];
    }

    Matrix operator * (const Matrix &b) const {
        Matrix c;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                for (int k = 0; k < N; ++k) {
                    c[i][k] += m[i][j] * b[j][k];
                }
            }
        }
        return c;
    }

    Matrix &operator *= (const Matrix &other) {
        *this = (*this) * other;
        return *this;
    }

    Matrix &operator *= (const T &x) {
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                m[i][j] *= x;
            }
        }
        return *this;
    }
    Matrix operator * (const T &x) const {
        Matrix a = *this;
        a *= x;
        return a;
    }

    Matrix &operator /= (const T &x) {
        T inv = T(1) / x;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                m[i][j] *= inv;
            }
        }
        return *this;
    }
    Matrix operator / (const T &x) const {
        Matrix a = *this;
        a /= x;
        return a;
    }

    Matrix &operator += (const Matrix &other) {
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                m[i][j] += other[i][j];
            }
        }
        return *this;
    }
    Matrix operator + (const Matrix &other) const {
        Matrix a = *this;
        a += other;
        return a;
    }

    Matrix &operator -= (const Matrix &other) {
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                m[i][j] -= other[i][j];
            }
        }
        return *this;
    }
    Matrix operator - (const Matrix &other) const {
        Matrix a = *this;
        a -= other;
        return a;
    }
};

template<typename T, int N>
Matrix<T, N> pow(Matrix<T, N> m, ll p) {
    Matrix<T, N> res = Matrix<T, N>::E();
    while (p) {
        if (p & 1) res *= m;
        m *= m;
        p >>= 1;
    }
    return res;
}

using M = Matrix<Mint, 4>;

int get_ind(int num, int b) {
    return (num == 1) + (b) * 2;
}

struct item {
    M m;

    template<typename T>
    void init(const T &t, int l, int r) {
        m = M();
        for (int prev = 0; prev < 2; ++prev) {
            for (int next = 0; next < 10; ++next) {
                if (prev == 1 && next == 3) continue;
                if (next <= t) {
                    m[get_ind(next, next == t)][get_ind(prev, 1)]++;
                }
                m[get_ind(next, 0)][get_ind(prev, 0)]++;
            }
        }
    }

    void update(const item &first, const item &second, int l, int r) {
        m = second.m * first.m;
    }

    static item merge(const item &first, const item &second, int l, int r) {
        item res;
        res.update(first, second, l, r);  // careful with different lengths
        return res;
    }
};

string to_string(const item &i) {
    stringstream ss;
    ss << "[" << "]";
    return ss.str();
}
ostream& operator << (ostream &o, const item &i) {
    return o << to_string(i);
}

struct segtree {
    vector<item> tree;
    int n = 1;

    segtree(int n = 1) : n(n) {
        tree.resize(1 << (__lg(max(1, n - 1)) + 2));
    }

    template<typename T>
    void build(const vector<T> &v, int i, int l, int r) {
        if (l == r) {
            tree[i].init(v[l], l, r);
            return;
        }
        int m = (l + r) >> 1;
        build(v, i * 2 + 1, l, m);
        build(v, i * 2 + 2, m + 1, r);
        tree[i].update(tree[i * 2 + 1], tree[i * 2 + 2], l, r);
    }

    template<typename T>
    void build(const vector<T> &v) {
        n = v.size();
        tree.resize(1 << (__lg(max(1, n - 1)) + 2));
        build(v, 0, 0, n - 1);
    }

    item ask(int l, int r, int i, int vl, int vr) {
        if (l == vl && r == vr) {
            return tree[i];
        }
        int m = (vl + vr) >> 1;
        if (r <= m) {
            return ask(l, r, i * 2 + 1, vl, m);
        } else if (m < l) {
            return ask(l, r, i * 2 + 2, m + 1, vr);
        } else {
            return item::merge(ask(l, m, i * 2 + 1, vl, m), ask(m + 1, r, i * 2 + 2, m + 1, vr), l, r);
        }
    }

    item ask(int l, int r) {
        l = max(l, 0); r = min(r, n - 1);
        if (l > r) return item();
        return ask(l, r, 0, 0, n - 1);
    }

    template<typename T>
    void set(int ind, const T &t) {
        static array<pair<int, int>, 30> st;
        int l = 0, r = n - 1, i = 0;
        int ptr = -1;
        while (l != r) {
            st[++ptr] = {l, r};
            int m = (l + r) >> 1;
            if (ind <= m) {
                i = i * 2 + 1;
                r = m;
            } else {
                i = i * 2 + 2;
                l = m + 1;
            }
        }
        tree[i].init(t, l, r);
        while (i != 0) {
            i = (i - 1) / 2;
            tree[i].update(tree[i * 2 + 1], tree[i * 2 + 2], st[ptr].first, st[ptr].second);
            --ptr;
        }
    }
};

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;

    vector<int> v;
    for (char c : s)
        v.pb(c - '0');
    segtree tree(n);
    tree.build(v);

    auto que = [&](int l, int r) {
        M m = tree.ask(l, r).m;
        Mint ans = 0;
        for (int i = 0; i < 4; ++i)
            ans += m[i][2];
        cout << ans << '\n';
    };

    que(0, n - 1);

    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int l, r;
            cin >> l >> r;
            --l; --r;
            que(l, r);
        } else {
            int ind, c;
            cin >> ind >> c;
            --ind;
            tree.set(ind, c);
        }
    }


    return 0;
}

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 1484 KB Output is correct
2 Correct 40 ms 2560 KB Output is correct

Subtask #4
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 1484 KB Output is correct
2 Correct 40 ms 2560 KB Output is correct
3 Correct 65 ms 17372 KB Output is correct
4 Correct 66 ms 17364 KB Output is correct
5 Correct 68 ms 17492 KB Output is correct
6 Correct 81 ms 17564 KB Output is correct
7 Correct 79 ms 17468 KB Output is correct

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 24 ms 1484 KB Output is correct
8 Correct 40 ms 2560 KB Output is correct
9 Correct 27 ms 1452 KB Output is correct
10 Correct 39 ms 2624 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 24 ms 1484 KB Output is correct
8 Correct 40 ms 2560 KB Output is correct
9 Correct 65 ms 17372 KB Output is correct
10 Correct 66 ms 17364 KB Output is correct
11 Correct 68 ms 17492 KB Output is correct
12 Correct 81 ms 17564 KB Output is correct
13 Correct 79 ms 17468 KB Output is correct
14 Correct 27 ms 1452 KB Output is correct
15 Correct 39 ms 2624 KB Output is correct
16 Correct 64 ms 17544 KB Output is correct
17 Correct 70 ms 17560 KB Output is correct
18 Correct 78 ms 17628 KB Output is correct
19 Correct 79 ms 17716 KB Output is correct
20 Correct 79 ms 17688 KB Output is correct