#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
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);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1920 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1920 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1920 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1920 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1920 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1920 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1920 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1920 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1095 ms |
3576 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1095 ms |
3576 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1920 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1920 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1920 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1920 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1920 KB |
Output is correct |
| 7 |
Execution timed out |
1095 ms |
3576 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1920 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1920 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1920 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1920 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1920 KB |
Output is correct |
| 7 |
Execution timed out |
1095 ms |
3576 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
