Submission #855810

#	Time	Username	Problem	Language	Result	Execution time	Memory
855810		divad	Lucky Numbers (RMI19_lucky)	C++14	14 / 100	1041 ms	27428 KiB

lucky

#include <bits/stdc++.h>
#define EQ 0
#define LE 1
#define state(x, y) x*10+y
using namespace std;
const int MOD = 1e9+7;
const int NMAX = 1e4+2;
const int SIGMA = 10;
const int LAT = 2*SIGMA;
int n,q,t,l,r,pos,val,dp[2][SIGMA][NMAX];
string str;

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] * aux.val[k][j];
                    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 <= 9; lst++){
                if(lst == 1 && dig == 3){
                    continue;
                }
                if(dig == str[pos]-'0'){
                    /// dp[EQ][dig][i] += dp[EQ][lst][i-1];
                    dp.val[state(EQ, lst)][state(EQ, dig)]++;
                    /// dp[prev_state][new_state] = 1
                }
                if(dig < str[pos]-'0'){
                    /// dp[LE][dig][i] += dp[EQ][lst][i-1];
                    dp.val[state(EQ, lst)][state(LE, dig)]++;
                }
                /// dp[LE][dig][i] += dp[LE][lst][i-1];
                dp.val[state(LE, lst)][state(LE, dig)]++;
            }
        }
    }

    int eval(){
        int ans = 0;
        for(int i = 0; i <= 9; 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];
    }
}

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

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

    cin >> n >> q;
    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: 0 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 27
• Subtask 5: 0 / 9
• Subtask 6: 0 / 27