시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
0.2 초 | 1024 MB | 3 | 2 | 2 | 100.000% |
It's a well known fact that in some cultures the number 13 brings bad luck.
You are given a number X consisting of N digits. You are to compute how many numbers smaller than or equal to X don't contain 13 as a substring in their base 10 representation. Since the answer can be quite large, you are to print it modulo 1 000 000 007.
In addition, you are to process Q queries of two possible types:
Note that number X is 1-indexed.
Note that number X and substr(X, l, r) may have leading zeros.
The first line of input contains two integers N and Q (1 ≤ N ≤ 100 000, 0 ≤ Q ≤ 10 000) - the number of digits of number X and the number of queries that need to be processed.
The second line of input contains the number X.
The next Q lines describe the queries that need to be processed. Each line starts with an integer t (1 ≤ t ≤ 2) - the type of query that needs to be processed.
If t = 1, then the line describes a Query and two integers radixL and radixR (1 ≤ radixL ≤ radixR ≤ N) follow - the left and right ends of the substring that you need to consider as bounds for the query.
Otherwise (t = 2), the line describes an Update and two integers radix and newDigit (1 ≤ radix ≤ N, 0 ≤ newDigit ≤ 9) follow - the position of the digit that needs to be changed and the new value of the digit.
The first line of the output contains a single integer - how many numbers smaller than or equal to X don't contain 13 as a substring in their base 10 representation. Since the answer can be quite large, you are to print it modulo 1 000 000 007.
Then, for each query of the first type, print the answer modulo 1 000 000 007 on a separate line.
번호 | 배점 | 제한 |
---|---|---|
1 | 14 | 1 ≤ N ≤ 6, Q = 0 |
2 | 14 | 1 ≤ N ≤ 18, Q = 0 |
3 | 9 | 1 ≤ N ≤ 10 000, 0 ≤ Q ≤ 10 000, all queries will be of the first type |
4 | 27 | 1 ≤ N ≤ 100 000, 0 ≤ Q ≤ 10 000, all queries will be of the first type |
5 | 9 | 1 ≤ N ≤ 10 000, 0 ≤ Q ≤ 10 000 |
6 | 27 | 1 ≤ N ≤ 100 000, 0 ≤ Q ≤ 10 000 |
6 10 560484 2 6 4 2 1 4 2 5 6 2 6 1 2 3 6 1 3 6 1 1 3 1 6 6 1 2 6 2 1 7
528145 6228 452 2 63454
There are 528145 non-negative integers smaller than or equal to 560484 not containing digits 13 as a substring in their base 10 representation. Note that this includes the number 0.
X is initially 560484.
After update "2 6 4", X becomes 560484.
After update "2 1 4", X becomes 460484.
After update "2 5 6", X becomes 460464.
After update "2 6 1", X becomes 460461.
After update "2 3 6", X becomes 466461.
Query "1 3 6" asks us how many non-negative integers smaller than or equal to 466461 don't contain substring 13 - there are 6228 such numbers.
Query "1 1 3" asks us how many non-negative integers smaller than or equal to 466461 not containing substring 13 - there are 452 such numbers.
Query "1 6 6" asks us how many non-negative integers smaller than or equal to 466461 not containing substring 13 - there are 2 such numbers: 0 and 1.
Query "1 2 6" asks us how many non-negative integers smaller than or equal to 466461 not containing substring 13 - there are 63454 such numbers. After update "2 1 7", X becomes 766461.