Submission #313866

#	Time	Username	Problem	Language	Result	Execution time	Memory
313866		MKopchev	Lucky Numbers (RMI19_lucky)	C++14	28 / 100	1093 ms	1680 KiB

lucky

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

const int nmax=1e5+42,mod=1e9+7;

int n,q;

int inp[nmax];

int LHS,RHS;

int dp[nmax][10][2];

int rec(int pos,int last_digit,int anything)
{
    if(pos>RHS)return 1;

    if(dp[pos-LHS][last_digit][anything]!=-1)return dp[pos-LHS][last_digit][anything];

    int ret=0;

    if(anything==0)
    {
        for(int cur=0;cur<=inp[pos];cur++)
            if(last_digit==1&&cur==3)continue;
            else
            {
                ret=ret+rec(pos+1,cur,cur<inp[pos]);
                if(ret>=mod)ret=ret-mod;
            }
    }
    else
    {
        for(int cur=0;cur<=9;cur++)
            if(last_digit==1&&cur==3)continue;
            else
            {
                ret=ret+rec(pos+1,cur,1);
                if(ret>=mod)ret=ret-mod;
            }
    }

    dp[pos-LHS][last_digit][anything]=ret;

    return ret;
}
int query(int l,int r)
{
    LHS=l;
    RHS=r;

    for(int t=0;t<=RHS-LHS+1;t++)
        for(int dig=0;dig<10;dig++)
            for(int low=0;low<2;low++)
                dp[t][dig][low]=-1;

    return rec(LHS,0,0);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie();
    cout.tie();

    cin>>n>>q;

    for(int i=1;i<=n;i++)
    {
        char c;
        cin>>c;
        inp[i]=c-'0';
    }

    cout<<query(1,n)<<"\n";

    for(int i=1;i<=q;i++)
    {
        int type;
        cin>>type;

        if(type==2)
        {
            int pos,val;
            cin>>pos>>val;

            inp[pos]=val;
        }
        else
        {
            int l,r;
            cin>>l>>r;

            cout<<query(l,r)<<"\n";
        }
    }
    return 0;
}

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