Submission #498197

#	Time	Username	Problem	Language	Result	Execution time	Memory
498197		couplefire	Lucky Numbers (RMI19_lucky)	C++17	100 / 100	86 ms	17680 KiB

lucky

#include <bits/stdc++.h>
using namespace std;

const int N = 1<<17;
const int MOD = 1000000007;

int add(int a, int b){return a+b>=MOD?a+b-MOD:a+b;}
void inc(int& a, int b){a=add(a, b);}
int sub(int a, int b){return a-b<0?a-b+MOD:a-b;}
void dec(int& a, int b){a=sub(a, b);}
int mul(int a, int b){return 1ll*a*b%MOD;}
void grow(int& a, int b){a=mul(a, b);}

int n, q, arr[N], dp[N<<1][4][4];

void init(int pos, int res[4][4]){
    for(int i = 0; i<4; ++i){
        for(int j = 0; j<4; ++j)
            res[i][j] = 0;
        bool eq = i/2;
        bool one = i%2;
        for(int k = 0; k<=(eq?arr[pos]:9); ++k){
            if(one && k==3) continue;
            inc(res[i][(eq&&k==arr[pos])*2+(k==1)], 1);
        }
    }
}

void comb(int a[4][4], int b[4][4], int res[4][4]){
    for(int i = 0; i<4; ++i)
        for(int j = 0; j<4; ++j){
            res[i][j] = 0;
            inc(res[i][j], mul(a[i][0], b[0][j]));
            inc(res[i][j], mul(a[i][1], b[1][j]));
            inc(res[i][j], mul(a[i][2], b[2][j]));
            inc(res[i][j], mul(a[i][3], b[3][j]));
        }
}

void build(int v, int tl, int tr){
    if(tl==tr) return init(tl, dp[v]);
    int tm = (tl+tr)>>1;
    build(v<<1, tl, tm); build(v<<1|1, tm+1, tr);
    comb(dp[v<<1], dp[v<<1|1], dp[v]);
}

void upd(int pos, int val, int v, int tl, int tr){
    if(tl==tr){arr[pos] = val; return init(tl, dp[v]);}
    int tm = (tl+tr)>>1;
    if(pos<=tm) upd(pos, val, v<<1, tl, tm);
    else upd(pos, val, v<<1|1, tm+1, tr);
    comb(dp[v<<1], dp[v<<1|1], dp[v]);
}

void query(int l, int r, int res[4][4], int v, int tl, int tr){
    if(l<=tl && tr<=r){
        for(int i = 0; i<4; ++i)
            for(int j = 0; j<4; ++j)
                res[i][j] = dp[v][i][j];
        return;
    }
    int tm = (tl+tr)>>1;
    if(r<=tm) query(l, r, res, v<<1, tl, tm);
    else if(l>tm) query(l, r, res, v<<1|1, tm+1, tr);
    else{
        int ll[4][4], rr[4][4];
        query(l, r, ll, v<<1, tl, tm);
        query(l, r, rr, v<<1|1, tm+1, tr);
        comb(ll, rr, res);
    }
}

int main(){
    // freopen("a.in", "r", stdin);
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> q; string s; cin >> s;
    for(int i = 1; i<=n; ++i)
        arr[i] = s[i-1]-'0';
    build(1, 1, n);
    for(int i = 0; i<=q; ++i){
        int t, x, y;
        if(!i) t = 1, x = 1, y = n;
        else cin >> t >> x >> y;
        if(t==1){
            int res[4][4];
            query(x, y, res, 1, 1, n);
            cout << add(add(res[2][0], res[2][1]), add(res[2][2], res[2][3])) << '\n';
        } else upd(x, y, 1, 1, n);
    }
}

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