Submission #272084

#TimeUsernameProblemLanguageResultExecution timeMemory
272084theStaticMindLucky Numbers (RMI19_lucky)C++14
100 / 100
15 ms4608 KiB
#include<bits/stdc++.h> #define pb push_back #define ii pair<int,int> #define all(x) (x).begin(),(x).end() #define sz(x) ((int)(x).size()) #define INF 100000000000000000 #define modulo 1000000007 #define mod 998244353 #define int long long int using namespace std; int dp[2][100005][2]; vector<int> arr(100005); int calculate(int l, int r){ int ret = 1; bool one = false; for(int i = l; i <= r; i++){ if(arr[i] == 1){ ret += (dp[0][r - i][0] + dp[0][r - i][1]); } else if(arr[i]){ ret += dp[1][r - i][0] + dp[1][r - i][1]; ret += (dp[0][r - i][0] + dp[0][r - i][1]) * max(0ll, arr[i] - 1 - (one && arr[i] > 3 ? 1 : 0)); } ret %= modulo; if(arr[i] == 1) one = true; else if(one && arr[i] == 3){ ret = (ret - 1 + modulo) % modulo; break; } else one = false; } return ret; } int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); dp[0][0][0] = 1; for(int i = 1; i <= 100000; i++){ dp[0][i][0] = (dp[0][i - 1][0] * 9 + dp[0][i - 1][1] * 8) % modulo; dp[0][i][1] = (dp[0][i - 1][0] + dp[0][i - 1][1]) % modulo; } dp[1][0][1] = 1; for(int i = 1; i <= 100000; i++){ dp[1][i][0] = (dp[1][i - 1][0] * 9 + dp[1][i - 1][1] * 8) % modulo; dp[1][i][1] = (dp[1][i - 1][0] + dp[1][i - 1][1]) % modulo; } int n, q; cin >> n >> q; string s; cin >> s; for(int i = 0; i < n; i++){ arr[i + 1] = s[i] - '0'; } cout << calculate(1, n) << "\n"; while(q--){ int t, x, y; cin >> t >> x >> y; if(t == 1){ cout << calculate(x, y) << "\n"; } else{ arr[x] = y; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...