Submission #640424

#	Time	Username	Problem	Language	Result	Execution time	Memory
640424		danikoynov	Lucky Numbers (RMI19_lucky)	C++14	100 / 100	56 ms	8732 KiB

lucky

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const ll mod = 1e9 + 7;
const int maxn = 1e5 + 10;

ll dp[maxn][10];
int n, q;
string num;
ll query(int l, int r)

{
    char c = num[l - 1];
    num[l - 1] = '#';
    ll ans = 0;
    bool fine = true;
    for (int j = l; j <= r; j ++)
    {
        for (int d = 0; d < (int)(num[j] - '0'); d ++)
        {
            if (num[j - 1] == '1' && d == 3)
                continue;
            ans = (ans + dp[r - j + 1][d]) % mod;
        }
        if (num[j - 1] == '1' && num[j] == '3')
        {
            fine = false;
            break;
        }
    }
    if (fine)
        ans = (ans + 1) % mod;
    num[l - 1] = c;
    return ans;
}
void solve()
{
    cin >> n >> q >> num;
    for (int i = 0; i < 10; i ++)
        dp[1][i] = 1;

    for (int i = 2; i < maxn; i ++)
    {
        ll sum = 0;
        for (int j = 0; j < 10; j ++)
            sum = (sum + dp[i - 1][j]) % mod;
        for (int j = 0; j < 10; j ++)
        {
            dp[i][j] = sum;
            if (j == 1)
                dp[i][j] = (dp[i][j] - dp[i - 1][3] + mod) % mod;
        }
    }

    num = "#" + num;
    cout << query(1, n) << endl;
    int type, l, r, pos, dig;
    for (int t = 1; t <= q; t ++)
    {
        cin >> type;
        if (type == 1)
        {
            cin >> l >> r;
            cout << query(l, r) << endl;
        }
        else
        {
            cin >> pos >> dig;
            num[pos] = (char)(dig + '0');
        }
    }
}

int main()
{
    solve();
    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