Submission #258686

#	Time	Username	Problem	Language	Result	Execution time	Memory
258686		cheeheng	Lucky Numbers (RMI19_lucky)	C++14	28 / 100	1095 ms	3576 KiB

lucky

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

using ll = long long;
typedef tuple<int, int, int, int> i4;
typedef tuple<ll, ll, ll, ll, ll, ll, ll, ll> i8;

const long long MOD = 1e9+7;

char S[100005];
int X[100005];
long long memo[100005][2];
long long dp2[100005][2];

int N, Q;
int K;

long long dp(int i, bool prev_digit_is_1, bool same_so_far){
    if(i == K){
        return 1;
    }else if(!same_so_far){
        if(prev_digit_is_1){
            return dp2[K-i][0];
        }else{
            return (dp2[K-i][1] + dp2[K-i][0])%MOD;
        }
    }else if(memo[i][prev_digit_is_1] != -1){
        return memo[i][prev_digit_is_1];
    }else{
        long long ans = 0;
        int j = X[i];
        if(j == 0){
            ans = dp(i+1, 0, 1);
        }else if(j == 1){
            ans = (dp(i+1, 0, 0) + dp(i+1, 1, 1))%MOD;
        }else if(j == 2){
            ans = (dp(i+1, 0, 0) + dp(i+1, 1, 0) + dp(i+1, 0, 1))%MOD;
        }else{
            ans = ((j-1-prev_digit_is_1)*dp(i+1, 0, 0) + dp(i+1, 1, 0) + dp(i+1, 0, 1))%MOD;
        }

        /*
        for(int j = 0; j < 10; j ++){
            if(j > X[i]){break;}
            if(prev_digit_is_1 && j == 3){
                continue;
            }

            ans += dp(i+1, j == 1, X[i] == j);
        }
        ans %= MOD;
        */

        //printf("memo[%d][%d][%d]=%lld\n", i, prev_digit_is_1, same_so_far, ans);
        return memo[i][prev_digit_is_1] = ans;
    }
}

// (first digit is 3, last digit is 1, same_so_far)
long long ways[5+(1<<18)][2][2][2];
int isMode[5+(1<<18)][2][2];

void init(int i = 1, int s = 0, int e = N-1){
    isMode[i][0][0] = (X[s] != 3 && X[e] != 1);
    isMode[i][0][1] = (X[s] != 3 && X[e] == 1);
    isMode[i][1][0] = (X[s] == 3 && X[e] != 1);
    isMode[i][1][1] = (X[s] == 3 && X[e] == 1);
    if(s == e){
        ways[i][0][0][0] = 8;
        ways[i][0][1][0] = 1;
        ways[i][1][0][0] = 1;
        ways[i][1][1][0] = 0;

        ways[i][0][0][1] = 0;
        ways[i][0][1][1] = 0;
        ways[i][1][0][1] = 0;
        ways[i][1][1][1] = 0;

        for(int j = 0; j <= X[s]; j ++){
            if(j == 3){
                ways[i][1][0][1] ++;
            }else if(j == 1){
                ways[i][0][1][1] ++;
            }else{
                ways[i][0][0][1] ++;
            }
        }
    }else{
        int l = (i<<1);
        int r = (i<<1)|1;
        int m = (s+e)>>1;

        init(l, s, m);
        init(r, m+1, e);

        /*
        22|22
        22|21
        22|32
        22|31
        21|22
        21|21

        32|22
        32|21
        32|32
        32|31
        31|22
        31|21

        (0, 0): 22|22, 22|32, 21|22
        (0, 1): 22|21, 22|31, 21|21
        (1, 0): 32|22, 32|32, 31|22
        (1, 1): 32|21, 32|31, 31|21

        */

        ways[i][0][0][0] = (ways[l][0][0][0]*ways[r][0][0][0] + ways[l][0][0][0]*ways[r][1][0][0]
                            + ways[l][0][1][0]*ways[r][0][0][0])%MOD;

        ways[i][0][1][0] = (ways[l][0][0][0]*ways[r][0][1][0] + ways[l][0][0][0]*ways[r][1][1][0]
                            + ways[l][0][1][0]*ways[r][0][1][0])%MOD;

        ways[i][1][0][0] = (ways[l][1][0][0]*ways[r][0][0][0] + ways[l][1][0][0]*ways[r][1][0][0]
                            + ways[l][1][1][0]*ways[r][0][0][0])%MOD;

        ways[i][1][1][0] = (ways[l][1][0][0]*ways[r][0][1][0] + ways[l][1][0][0]*ways[r][1][1][0]
                            + ways[l][1][1][0]*ways[r][0][1][0])%MOD;


        ways[i][0][0][1] = 0;
        ways[i][0][1][1] = 0;
        ways[i][1][0][1] = 0;
        ways[i][1][1][1] = 0;

        for(int a = 0; a < 2; a ++){
            for(int b = 0; b < 2; b ++){
                for(int c = 0; c < 2; c ++){
                    if(b&&c){continue;}
                    for(int d = 0; d < 2; d ++){
                        if( isMode[l][a][b] ){
                            ways[i][a][d][1] += (ways[l][a][b][1]+MOD-1)*ways[r][c][d][0]%MOD;
                            ways[i][a][d][1] += ways[r][c][d][1];
                        }else{
                            ways[i][a][d][1] += ways[l][a][b][1]*ways[r][c][d][0]%MOD;
                        }
                    }
                }
            }
        }

        ways[i][0][0][1] %= MOD;
        ways[i][0][1][1] %= MOD;
        ways[i][1][0][1] %= MOD;
        ways[i][1][1][1] %= MOD;

    }
    for(int j = 0; j < 8; j ++){
        //printf("s=%d e=%d [%d][%d][%d]: %lld\n", s, e, (int)((j&4)!=0), (int)((j&2)!=0), j&1, ways[i][(j&4)!=0][(j&2)!=0][j&1]);
    }
}

int k = 0;
long long tempL[31][2][2][2];
long long tempR[31][2][2][2];
long long newWays[31][2][2][2];
int isMode2[31][2][2];

i8 query(int x, int y, int i = 1, int s = 0, int e = N-1){
    if(s == 0 && e == N-1){k = 0;memset(newWays, 0, sizeof(newWays));}
    if(x <= s && e <= y){
        return i8(ways[i][0][0][0], ways[i][0][0][1], ways[i][0][1][0], ways[i][0][1][1],
                  ways[i][1][0][0], ways[i][1][0][1], ways[i][1][1][0], ways[i][1][1][1]);
    }else{
        int l = (i<<1);
        int r = (i<<1)|1;
        int m = (s+e)>>1;

        if(x > m){
            return query(x, y, r, m+1, e);
        }else if(y <= m){
            return query(x, y, l, s, m);
        }else{
            int cnt = k;
            k ++;

            i8 l1 = query(x, y, l, s, m);
            i8 r1 = query(x, y, r, m+1, e);

            int tempIndx = min(m, y);
            isMode2[cnt][0][0] = (X[x] != 3 && X[tempIndx] != 1);
            isMode2[cnt][0][1] = (X[x] != 3 && X[tempIndx] == 1);
            isMode2[cnt][1][0] = (X[x] == 3 && X[tempIndx] != 1);
            isMode2[cnt][1][1] = (X[x] == 3 && X[tempIndx] == 1);

            tempL[cnt][0][0][0] = get<0>(l1);
            tempL[cnt][0][0][1] = get<1>(l1);
            tempL[cnt][0][1][0] = get<2>(l1);
            tempL[cnt][0][1][1] = get<3>(l1);
            tempL[cnt][1][0][0] = get<4>(l1);
            tempL[cnt][1][0][1] = get<5>(l1);
            tempL[cnt][1][1][0] = get<6>(l1);
            tempL[cnt][1][1][1] = get<7>(l1);

            tempR[cnt][0][0][0] = get<0>(r1);
            tempR[cnt][0][0][1] = get<1>(r1);
            tempR[cnt][0][1][0] = get<2>(r1);
            tempR[cnt][0][1][1] = get<3>(r1);
            tempR[cnt][1][0][0] = get<4>(r1);
            tempR[cnt][1][0][1] = get<5>(r1);
            tempR[cnt][1][1][0] = get<6>(r1);
            tempR[cnt][1][1][1] = get<7>(r1);

            newWays[cnt][0][0][0] = (tempL[cnt][0][0][0]*tempR[cnt][0][0][0] + tempL[cnt][0][0][0]*tempR[cnt][1][0][0]
                                + tempL[cnt][0][1][0]*tempR[cnt][0][0][0])%MOD;

            newWays[cnt][0][1][0] = (tempL[cnt][0][0][0]*tempR[cnt][0][1][0] + tempL[cnt][0][0][0]*tempR[cnt][1][1][0]
                                + tempL[cnt][0][1][0]*tempR[cnt][0][1][0])%MOD;

            newWays[cnt][1][0][0] = (tempL[cnt][1][0][0]*tempR[cnt][0][0][0] + tempL[cnt][1][0][0]*tempR[cnt][1][0][0]
                                + tempL[cnt][1][1][0]*tempR[cnt][0][0][0])%MOD;

            newWays[cnt][1][1][0] = (tempL[cnt][1][0][0]*tempR[cnt][0][1][0] + tempL[cnt][1][0][0]*tempR[cnt][1][1][0]
                                + tempL[cnt][1][1][0]*tempR[cnt][0][1][0])%MOD;

            for(int a = 0; a < 2; a ++){
                for(int b = 0; b < 2; b ++){
                    for(int c = 0; c < 2; c ++){
                        if(b&&c){continue;}
                        for(int d = 0; d < 2; d ++){
                            if(isMode2[cnt][a][b]){
                                newWays[cnt][a][d][1] += (tempL[cnt][a][b][1]+MOD-1)*tempR[cnt][c][d][0]%MOD;
                                newWays[cnt][a][d][1] += tempR[cnt][c][d][1];
                            }else{
                                newWays[cnt][a][d][1] += tempL[cnt][a][b][1]*tempR[cnt][c][d][0]%MOD;
                            }
                        }
                    }
                }
            }

            return i8(newWays[cnt][0][0][0], newWays[cnt][0][0][1], newWays[cnt][0][1][0], newWays[cnt][0][1][1],
                  newWays[cnt][1][0][0], newWays[cnt][1][0][1], newWays[cnt][1][1][0], newWays[cnt][1][1][1]);
        }
    }
}

int main(){
    scanf("%d%d", &N, &Q);
    scanf(" %s", S);

    for(int i = 0; i < N; i ++){
        X[i] = S[i]-'0';
    }

    dp2[0][0] = 1;
    dp2[0][1] = 0;
    for(int i = 1; i <= N; i ++){
        dp2[i][0] = (dp2[i-1][1]*8 + dp2[i-1][0]*9)%MOD;
        dp2[i][1] = (dp2[i-1][1] + dp2[i-1][0])%MOD;
        //printf("dp2[%d][%d]=%lld\n", i, 0, dp2[i][0]);
        //printf("dp2[%d][%d]=%lld\n", i, 1, dp2[i][1]);
    }

    K = N;
    memset(memo, -1, sizeof(memo));
    //printf("%lld\n", dp(0, false, true));
    init();
    i8 temp = query(0, N-1);
    long long ans = 0;
    ans += get<1>(temp);
    ans += get<3>(temp);
    ans += get<5>(temp);
    ans += get<7>(temp);
    ans %= MOD;
    printf("%lld\n", ans);

    for(int i = 0; i < Q; i ++){
        int t, l, r;
        scanf("%d%d%d", &t, &l, &r);

        if(t == 2){
            S[l-1] = r+'0';
            X[l-1] = r;
            init();
        }else{
            //printf("%s\n", S);


            l --;
            r --;
            for(int j = 0; j < r-l+1; j ++){
                X[j] = S[l+j]-'0';
            }
            K = r-l+1;
            //memset(memo, -1, sizeof(memo));

            init();
            i8 temp = query(0, K-1);
            long long ans = 0;
            ans += get<1>(temp);
            ans += get<3>(temp);
            ans += get<5>(temp);
            ans += get<7>(temp);
            ans %= MOD;
            //assert(ans >= 0);
            printf("%lld\n", ans);
            //printf("%lld\n", dp(0, false, true));
        }
    }

    return 0;
}

Compilation message (stderr)

lucky.cpp: In function 'int main()':
lucky.cpp:249:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &Q);
     ~~~~~^~~~~~~~~~~~~~~~
lucky.cpp:250:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %s", S);
     ~~~~~^~~~~~~~~~
lucky.cpp:280:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &t, &l, &r);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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