Submission #302890

#	Time	Username	Problem	Language	Result	Execution time	Memory
302890		2fat2code	Lucky Numbers (RMI19_lucky)	C++17	100 / 100	64 ms	8724 KiB

lucky

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define sz() size()
#define fr first
#define sc second
#define int long long
//#define mp make_pair
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)

const int mod = 1e9 + 7;
const int nmax = 100005;

int n,q,dp[nmax][10],ans;
string s;

void add(int &a,int b){
    a = (a + b) % mod;
}

void calc(int digitleft,int pos,int prevdigit){
    for(int t=0;t<(int)(s[pos] - '0');t++){
        if(prevdigit == 1 && t == 3) continue;
        add(ans,dp[digitleft][t]);
    }
    if((int)(s[pos] - '0') == 3 && prevdigit == 1){
        return;
    }
    else if(digitleft == 1){
        add(ans,1LL);
        return;
    }
    else{
        calc(digitleft - 1, pos + 1, (int)(s[pos] - '0'));
    }
}

void precalc(){
    for(int i=0;i<=9;i++) dp[1][i] = 1;
    for(int i=2;i<=100000;i++){
        for(int j=0;j<=9;j++){
            for(int t=0;t<=9;t++){
                if(j == 1 && t == 3) continue;
                else{
                    add(dp[i][j],dp[i-1][t]);
                }
            }
        }
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
    srand(chrono::steady_clock::now().time_since_epoch().count());
    cin >> n >> q >> s;
    precalc();
    ans = 0;
    calc(n,0,-1);
    cout << ans << '\n';
    for(int i=1;i<=q;i++){
        int type;
        cin >> type;
        if(type == 1){
            int l,r;
            cin >> l >> r;
            --l;
            --r;
            ans = 0;
            calc(r-l+1,l,-1);
            cout << ans << '\n';
        }
        else{
            int l;
            char r;
            cin >> l >> r;
            s[l - 1] = r;
        }
    }
}

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