Submission #1119705

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119705		MateiKing80	Lucky Numbers (RMI19_lucky)	C++14	100 / 100	37 ms	20560 KiB

lucky

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define int ll


const int mod = 1e9 + 7, N = 1e5;
const int mod2 = mod * mod;

string s;

int p10[2][2][N + 5];
struct nod
{
    int dp[2][2];
    int cifrafata, cifraspate, are13, lg;
};
nod aint[4 * N + 5];

void print(nod x)
{

}

nod cif(int x)
{
    nod a;
    a.dp[0][0] = x;
    if(x > 3)
        a.dp[1][0] = 1;
    else
        a.dp[1][0] = 0;
    if(x > 1)
        a.dp[0][1] = 1;
    else
        a.dp[0][1] = 0;
    a.dp[1][1] = 0;
    a.cifrafata = x;
    a.cifraspate = x;
    a.are13 = 0;
    a.lg = 1;
    return a;
}

nod join(nod a, nod b)
{
    nod c;
    c.cifrafata = a.cifrafata;
    c.cifraspate = b.cifraspate;
    if(a.cifraspate == 1 && b.cifrafata == 3)
        c.are13 = 1;
    else
        c.are13 = (a.are13 | b.are13);
    c.lg = a.lg + b.lg;

    for(auto i : {0, 1})
        for(auto j : {0, 1})
        {
            if(a.are13 || (i == 1 && a.cifrafata != 3))
                c.dp[i][j] = (a.dp[i][0] * p10[0][j][b.lg] - a.dp[i][1] * p10[1][j][b.lg] + mod2) % mod;
            else
            {
                if(a.cifraspate == 1)
                    c.dp[i][j] = (a.dp[i][0] * p10[0][j][b.lg] - a.dp[i][1] * p10[1][j][b.lg] + b.dp[0][j] - b.dp[1][j] + mod2) % mod;
                else
                    c.dp[i][j] = (a.dp[i][0] * p10[0][j][b.lg] - a.dp[i][1] * p10[1][j][b.lg] + b.dp[0][j] + mod2) % mod;
            }
        }
    return c;
}

#define mid (st + dr) / 2

void update(int pos, int st, int dr, int l, int val)
{
    if(st == dr)
    {
        aint[pos] = cif(val);
        return;
    }
    if(l <= mid)
        update(2 * pos, st, mid, l, val);
    else
        update(2 * pos + 1, mid + 1, dr, l, val);
    aint[pos] = join(aint[2 * pos], aint[2 * pos + 1]);
}

nod query(int pos, int st, int dr, int l, int r)
{
    if(l <= st && dr <= r)
        return aint[pos];
    if(r <= mid)
        return query(2 * pos, st, mid, l, r);
    if(mid < l)
        return query(2 * pos + 1, mid + 1, dr, l, r);
    return join(query(2 * pos, st, mid, l, r), query(2 * pos + 1, mid + 1, dr, l, r));
}

void build(int pos, int st, int dr)
{
    if(st == dr)
    {
        aint[pos] = cif(s[st] - '0');
        return;
    }
    build(2 * pos, st, mid);
    build(2 * pos + 1, mid + 1, dr);
    aint[pos] = join(aint[2 * pos], aint[2 * pos + 1]);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    p10[0][0][0] = 1;
    p10[0][0][1] = 10;
    p10[1][0][1] = 1;
    p10[0][1][1] = 1;
    p10[1][1][1] = 0;
    for(int i = 2; i <= N; i ++)
    {
        p10[0][0][i] = (p10[0][0][i - 1] * 10 - p10[1][0][i - 1] + mod2) % mod;
        p10[1][0][i] = p10[0][0][i - 1];
        p10[0][1][i] = p10[0][0][i - 1];
        p10[1][1][i] = p10[0][0][i - 2];
    }
    int n, q;
    cin >> n >> q >> s;
    s = "#" + s;
    build(1, 1, n);
    auto x = query(1, 1, n, 1, n);
    cout << x.dp[0][0] + 1 - x.are13 << '\n';
    for(int i = 0; i < q; i ++)
    {
        int t, l, r;
        cin >> t >> l >> r;
        if(t == 1)
        {
            auto y = query(1, 1, n, l, r);
            cout << y.dp[0][0] + 1 - y.are13 << '\n';
        }
        else
            update(1, 1, n, l, r);
    }
}
/*
putem face un aint in care sa tinem in stanga nr de numere pe care le putem face fara 13
in dreapta la fel
si mai tinem cate nr fara 13 putem face a.i. ultima cifra sa fie 1
si cate nr fara 13 putem face a.i. ultima cifra sa fie 3
si cred ca ne trebuie si cate putem face a.i. prima cifra sa fie 1 si ultima fie 3
also ne trebuie o precalculare pentru cate numere pana in 10^x nu au 13
cate numere pana in 10^x nu au 13 si au 1 prima cifra si cate numere pana in 10^x nu au 13 si au 3 ultima cifra

fata inseamna sa aiba prima cifra 3 dar nicaieri 13
spate inseamna sa aiba prima cifra 1 dar nicaieri 13


c.nrtotal
daca a are deja 13
    a.nrtotal * p10[b.nrcif] - a.spate * p10fata[b.nrcif];
altfel
    daca a are ultima cifra 1
        a.nrtotal * p10[b.nrcif] - a.spate * p10fata[b.nrcif] + b.nrtotal - b.fata
    altfel
        a.nrtotal * p10[b.nrcif] - a.spate * p10fata[b.nrcif] + b.nrtotal

c.fata
daca a are deja 13
    a.fata * p10[b.nrcif] - a.spate * p10fata[b.nrcif];
altfel
    daca a are ultima cifra 1
        a.fata * p10[b.nrcif] - a.spate * p10fata[b.nrcif] + b.nrtotal - b.fata
    altfel
        a.fata * p10[b.nrcif] - a.spate * p10fata[b.nrcif] + b.nrtotal

c.spate
daca a are deja 13
    a.nrtotal * p10spate[b.nrcif] - a.spate * p10fataspate[b.nrcif];
altfel
    daca a are ultima cifra 1
        a.nrtotal * p10spate[b.nrcif] - a.spate * p10fataspate[b.nrcif] + b.spate - b.fataspate
    altfel
        a.nrtotal * p10spate[b.nrcif] - a.spate * p10fataspate[b.nrcif] + b.spate

c.fataspate
daca a are deja 13
    a.fata * p10spate[b.nrcif] - a.fataspate * p10fataspate[b.nrcif];
altfel
    daca a are ultima cifra 1
        a.fata * p10spate[b.nrcif] - a.fataspate * p10fataspate[b.nrcif] + b.spate - b.fataspate
altfel
        a.fata * p10spate[b.nrcif] - a.fataspate * p10fataspate[b.nrcif] + b.spate
*/

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