Submission #856233

#	Time	Username	Problem	Language	Result	Execution time	Memory
856233		divad	Lucky Numbers (RMI19_lucky)	C++14	100 / 100	81 ms	17496 KiB

lucky

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,O3,unroll-loops,fast-math")
#pragma GCC target("avx2")
#define EQ 0
#define LE 1
#define state(x, y) x*2+y
#define typedig(x) (x == 1 ? 0 : (x == 3 ? 1 : 1) )
using namespace std;
const int MOD = 1e9+7;
const int NMAX = 1e5+2;
const int LAT = 2*2;
int n,q,t,l,r,pos,val;
int nr_loop;
string str;

ifstream fin("test.in");
ofstream fout("test.out");

struct Mat {
    int val[LAT][LAT] = {0};
    void reset(){
        memset(val, 0, sizeof(val));
    }

    void fill_diag(){
        for(int i = 0; i < LAT; i++){
            val[i][i] = 1;
        }
    }

    Mat operator * (const Mat &aux) const {
        Mat ans;
        for(int i = 0; i < LAT; i++){
            for(int j = 0; j < LAT; j++){
                for(int k = 0; k < LAT; k++){
                    ans.val[i][j] += (val[i][k] * 1ll * aux.val[k][j])%MOD;
                    ans.val[i][j] %= MOD;
                }
            }
        }
        return ans;
    }

};

struct Node {
    Mat dp;
    void init(int pos){
        dp.reset();
        for(int dig = 0; dig <= 9; dig++){
            for(int lst = 0; lst <= 1; lst++){
                if(lst == 0 && dig == 3){
                    continue;
                }
                if(dig == str[pos]-'0'){
                    dp.val[state(EQ, lst)][state(EQ, typedig(dig))]++;
                }
                if(dig < str[pos]-'0'){
                    dp.val[state(EQ, lst)][state(LE, typedig(dig))]++;
                }
                dp.val[state(LE, lst)][state(LE, typedig(dig))]++;
            }
        }
    }

    int eval(){
        int ans = 0;
        for(int i = 0; i <= 1; i++){
            ans += dp.val[0][state(LE, i)] + dp.val[0][state(EQ, i)];
            ans %= MOD;
        }
        return ans;
    }

    Node operator + (const Node &aux) const {
        Node ans;
        ans.dp = dp * aux.dp;
        return ans;
    }
} aint[4*NMAX];

void build(int nod, int st, int dr){
    if(st == dr){
        aint[nod].init(st);
    }else{
        int mid = (st+dr)/2;
        build(2*nod, st, mid);
        build(2*nod+1, mid+1, dr);
        aint[nod] = aint[2*nod] + aint[2*nod+1];
    }
}

Node query(int nod, int st, int dr, int l, int r){
    if(l <= st && dr <= r){
        return aint[nod];
    }else{
        int mid = (st+dr)/2;
        Node lson, rson;
        lson.dp.fill_diag();
        rson.dp.fill_diag();

        if(l <= mid){
            lson = query(2*nod, st, mid, l, r);
        }
        if(r >= mid+1){
            rson = query(2*nod+1, mid+1, dr, l, r);
        }

        return lson + rson;
    }
}

void update(int nod, int st, int dr, int pos){
    if(st == dr){
        aint[nod].init(st);
    }else{
        int mid = (st+dr)/2;
        if(pos <= mid){
            update(2*nod, st, mid, pos);
        }else{
            update(2*nod+1, mid+1, dr, pos);
        }
        aint[nod] = aint[2*nod] + aint[2*nod+1];
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
#ifdef ONPC
    #define cin fin
    #define cout fout
#endif // ONPC
    cin.tie(nullptr);
    cout.tie(nullptr);

    Node aux;
    aux.dp.val[0][state(EQ, 1)] = 1;

    cin >> n >> q;
    cin.ignore();
    getline(cin, str);
    str = "$"+str;
    build(1, 1, n);
    cout << (aux + aint[1]).eval() << "\n";
    while(q--){
        cin >> t;
        if(t == 1){
            cin >> l >> r;
            Node ans = query(1, 1, n, l, r);
            cout << (aux + ans).eval() << "\n";
        }else{
            cin >> pos >> val;
            str[pos] = (val+'0');
            update(1, 1, n, pos);
        }
    }
    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 27 / 27
• Subtask 5: 9 / 9
• Subtask 6: 27 / 27