Submission #313876

#	Time	Username	Problem	Language	Result	Execution time	Memory
313876		MKopchev	Lucky Numbers (RMI19_lucky)	C++14	100 / 100	85 ms	4992 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];//digits, first digit

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

    int ret=0,prv=0;

    for(int i=LHS;i<=RHS;i++)
    {
        for(int cur=0;cur<inp[i];cur++)
            if(prv==1&&cur==3)continue;
            else
            {
                ret=(ret+dp[RHS-i][cur])%mod;
            }

        if(prv==1&&inp[i]==3)break;

        prv=inp[i];

        if(i==RHS)ret=(ret+1)%mod;
    }

    return ret;
}

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

    cin>>n>>q;

    for(int i=0;i<=9;i++)
    {
        dp[0][i]=1;
    }

    for(int pos=1;pos<=n;pos++)
    {
        for(int frst=0;frst<=9;frst++)
        {
            for(int prv=0;prv<=9;prv++)
                if(frst==1&&prv==3)continue;
                else
                {
                    dp[pos][frst]=(dp[pos][frst]+dp[pos-1][prv])%mod;
                }
            //cout<<pos<<" "<<frst<<" -> "<<dp[pos][frst]<<endl;
        }
    }


    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: 9 / 9
• Subtask 4: 27 / 27
• Subtask 5: 9 / 9
• Subtask 6: 27 / 27