# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
864490 | 2023-10-23T04:44:11 Z | AgentPengin | Lucky Numbers (RMI19_lucky) | C++14 | 0 ms | 0 KB |
#include<bits/stdc++.h> using namespace std; #define read() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define day() time_t now = time(0);char* x = ctime(&now);cerr<<"Right Now Is : "<<x<<"\n" #define ii pair<int,int> #define X first #define Y second const long long MAX = (int)2e5 + 5; const long long INF = (int)1e9; const long long MOD = (int)1e9 + 7; int n,q; int a[MAX]; int visited[MAX][2][2]; int dp[MAX][2][2]; int times = 0; int f(int id,int l,int r,bool last,bool lower){ if(id + l > r)return 1; if(visited[id][last][lower] == times)return dp[id][last][lower]; visited[id][last][lower] = times; int &res = dp[id][last][lower] = 0; for(int digit = 0;digit < 10;digit++){ if(!lower && digit > a[id + l])continue; if(last && digit == 3)continue; res = (res + f(id + 1,l,r,digit == 1,lower || digit < a[id + l])) % MOD; } return res; } signed main(){ read(); cin >> n >> q; for(int i = 1;i <= n;i++){ char x; cin >> x; a[i] = x - '0'; } times++; cout << f(0,u,v,0,0) << '\n'; for(int i = 1,c,u,v;i <= q;i++){ cin >> c >> u >> v; if(c == 1){ times++; cout << f(0,u,v,0,0) << '\n'; }else{ a[u] = v; } } }