Submission #1198013

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198013		12345678	Lucky Numbers (RMI19_lucky)	C++20	100 / 100	125 ms	51472 KiB

lucky

#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5, mod=1e9+7;

#define ll long long

ll n, q, t, l, r, str[nx], f, pre[10][4][4]; // dp[digit][not 3 / anything][tight?]
char c;

void precompute()
{
    for (int cur=0; cur<=9; cur++)
    {
        for (int i=0; i<4; i++)
        {
            int any=i%2, tight=i/2;
            int lb=0, ub=tight?cur:9;
            for (int d=lb; d<=ub; d++)
            {
                if (any)
                {
                    if (d==1) pre[cur][i][2*(tight&(d==ub))]++;
                    else pre[cur][i][2*(tight&(d==ub))+1]++;
                }
                else
                {
                    if (d!=3)
                    {
                        if (d==1) pre[cur][i][2*(tight&(d==ub))]++;
                        else pre[cur][i][2*(tight&(d==ub))+1]++;
                    }
                }
            }
        }
    }
}

struct segtree
{
    struct node
    {
        ll mat[4][4];
        node()
        {
            for (int i=0; i<4; i++) for (int j=0; j<4; j++) mat[i][j]=0;
        }
        node(int x)
        {
            for (int i=0; i<4; i++) for (int j=0; j<4; j++) mat[i][j]=pre[x][i][j];
        }
    } d[4*nx];
    node identity()
    {
        node res;
        for (int i=0; i<4; i++) res.mat[i][i]=1;
        return res;
    }
    node merge(node lhs, node rhs)
    {
        node res;
        for (int i=0; i<4; i++) for (int j=0; j<4; j++) for (int k=0; k<4; k++) res.mat[i][j]=(res.mat[i][j]+lhs.mat[i][k]*rhs.mat[k][j])%mod;
        return res; 
    }
    void build(int l, int r, int i)
    {
        if (l==r) return d[i]=node(str[l]), void();
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
        d[i]=merge(d[2*i], d[2*i+1]);
    }
    void update(int l, int r, int i, int idx, int vl)
    {
        if (idx<l||r<idx) return;
        if (l==r) return d[i]=node(vl), void();
        int md=(l+r)/2;
        update(l, md, 2*i, idx, vl);
        update(md+1, r, 2*i+1, idx, vl);
        d[i]=merge(d[2*i], d[2*i+1]);
    }
    node query(int l, int r, int i, int ql, int qr)
    {
        if (qr<l||r<ql) return identity();
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return merge(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
    }
} s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>q;
    q++;
    for (int i=1; i<=n; i++) cin>>c, str[i]=c-'0';
    precompute();
    s.build(1, n, 1);
    while (q--)
    {
        if (!f) f=1, t=1, l=1, r=n;
        else cin>>t>>l>>r;
        if (t==1)
        {
            auto tmp=s.query(1, n, 1, l, r);
            ll res=0;
            for (int i=0; i<4; i++) res=(res+tmp.mat[3][i])%mod;
            cout<<res<<'\n';
        }
        else s.update(1, n, 1, l, 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