#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9+7;
char S[100005];
int X[100005];
long long memo[10005][2][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(memo[i][prev_digit_is_1][same_so_far] != -1){
return memo[i][prev_digit_is_1][same_so_far];
}else if(!same_so_far){
long long ans = 0;
for(int j = 0; j < 10; j ++){
if(prev_digit_is_1 && j == 3){
continue;
}
ans += dp(i+1, j == 1, false);
}
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][same_so_far] = ans;
}else{
long long ans = 0;
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][same_so_far] = ans;
}
}
int main(){
scanf("%d%d", &N, &Q);
scanf(" %s", S);
for(int i = 0; i < N; i ++){
X[i] = S[i]-'0';
}
memset(memo, -1, sizeof(memo));
/*dp2[1][1] = 1;
dp2[1][2] = 9;
for(int i = 2; 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;
}*/
K = N;
memset(memo, -1, sizeof(memo));
printf("%lld\n", dp(0, false, true));
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';
}else{
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));
printf("%lld\n", dp(0, false, true));
}
}
return 0;
}
Compilation message
lucky.cpp: In function 'int main()':
lucky.cpp:50: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:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %s", S);
~~~~~^~~~~~~~~~
lucky.cpp:72: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);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
640 KB |
Output is correct |
2 |
Correct |
1 ms |
640 KB |
Output is correct |
3 |
Correct |
1 ms |
640 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
640 KB |
Output is correct |
2 |
Correct |
1 ms |
640 KB |
Output is correct |
3 |
Correct |
1 ms |
640 KB |
Output is correct |
4 |
Correct |
1 ms |
672 KB |
Output is correct |
5 |
Correct |
1 ms |
640 KB |
Output is correct |
6 |
Correct |
1 ms |
640 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1089 ms |
1656 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1089 ms |
1656 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
640 KB |
Output is correct |
2 |
Correct |
1 ms |
640 KB |
Output is correct |
3 |
Correct |
1 ms |
640 KB |
Output is correct |
4 |
Correct |
1 ms |
672 KB |
Output is correct |
5 |
Correct |
1 ms |
640 KB |
Output is correct |
6 |
Correct |
1 ms |
640 KB |
Output is correct |
7 |
Execution timed out |
1089 ms |
1656 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
640 KB |
Output is correct |
2 |
Correct |
1 ms |
640 KB |
Output is correct |
3 |
Correct |
1 ms |
640 KB |
Output is correct |
4 |
Correct |
1 ms |
672 KB |
Output is correct |
5 |
Correct |
1 ms |
640 KB |
Output is correct |
6 |
Correct |
1 ms |
640 KB |
Output is correct |
7 |
Execution timed out |
1089 ms |
1656 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |