| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 258142 |
2020-08-05T12:32:04 Z |
lyc |
Lucky Numbers (RMI19_lucky) |
C++14 |
|
18 ms |
1792 KB |
#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
using ll=long long;
const int mxN = 1e5+5;
const int mod = 1e9+7;
int N, Q;
string X;
int f[mxN][2][2];
using Data = array<array<array<int,2>,2>,2>; // bound, start 3, end 1;
struct node {
int s, e, m;
Data v;
node *l, *r;
void setLeaf(char c) {
X[s] = c;
v[1][0][0] = (c != '3' && c != '1');
v[1][0][1] = (c == '1');
v[1][1][0] = (c == '3');
v[1][1][1] = 0;
int u = c-'0';
v[0][0][0] = u - (c > '3') - (c > '1');
v[0][0][1] = (c > '1');
v[0][1][0] = (c > '3');
v[0][1][1] = 0;
//~ cout << "SET" _ s _ c << " :: ";
//~ FOR(x,0,1) FOR(y,0,1) FOR(z,0,1) cout << v[x][y][z] << ' ';
//~ cout << endl;
}
inline Data merge(int L, int R, Data a, Data b) {
Data u;
int lenb = R-m;
FOR(i,0,1){
FOR(j,0,1){
u[1][i][j] = (ll) a[1][i][0] * b[1][0][j] % mod;
u[1][i][j] += (ll) a[1][i][0] * b[1][1][j] % mod;
u[1][i][j] %= mod;
u[1][i][j] += (ll) a[1][i][1] * (lenb==1&&j?0:b[1][0][j]) % mod;
u[1][i][j] %= mod;
}
}
FOR(i,0,1){
FOR(j,0,1){
u[0][i][j] = (ll) a[0][i][0] * f[lenb][0][j] % mod;
u[0][i][j] += (ll) a[0][i][0] * f[lenb][1][j] % mod;
u[0][i][j] %= mod;
u[0][i][j] += (ll) a[0][i][1] * f[lenb][0][j] % mod;
u[0][i][j] %= mod;
u[0][i][j] += (ll) a[1][i][0] * b[0][0][j] % mod;
u[0][i][j] %= mod;
u[0][i][j] += (ll) a[1][i][0] * b[0][1][j] % mod;
u[0][i][j] %= mod;
u[0][i][j] += (ll) a[1][i][1] * (lenb==1&&j?0:b[0][0][j]) % mod;
u[0][i][j] %= mod;
}
}
//~ cout << "MERGE" _ L _ R << " :: ";
//~ FOR(x,0,1) FOR(y,0,1) FOR(z,0,1) cout << u[x][y][z] << ' ';
//~ cout << endl;
return u;
}
node(int s, int e): s(s), e(e), m((s+e)/2) {
if (s == e) setLeaf(X[s]);
else {
l = new node(s,m), r = new node(m+1,e);
v = merge(s,e,l->v,r->v);
}
//~ cout << s _ e << " :: ";
//~ FOR(x,0,1) FOR(y,0,1) FOR(z,0,1) cout << v[x][y][z] << ' ';
//~ cout << endl;
}
void update(int a, char b) {
if (s == e) { setLeaf(b); return; }
else if (a <= m) l->update(a,b);
else r->update(a,b);
v = merge(s,e,l->v,r->v);
}
Data query(int a, int b) {
if (s == a && e == b) return v;
if (b <= m) return l->query(a,b);
if (a > m) return r->query(a,b);
return merge(s, e, l->query(a,m), r->query(m+1,b));
}
} *root;
void answer(int L, int R) {
Data res = root->query(L,R);
int ans = 0;
//~ FOR(x,0,1) FOR(y,0,1) FOR(z,0,1) cout << res[x][y][z] << ' ';
//~ cout << " :: ";
FOR(a,0,1) FOR(b,0,1) FOR(c,0,1) ans = (ans+res[a][b][c])%mod;
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> N >> Q >> X;
X = '^' + X;
f[0][0][0] = 1;
f[0][0][1] = f[0][1][0] = f[0][1][1] = 0;
f[1][0][0] = 8;
f[1][0][1] = f[1][1][0] = 1;
f[1][1][1] = 0;
FOR(i,2,N){
f[i][0][0] = (ll) f[i-1][0][0] * 9 % mod;
f[i][0][0] += (ll) f[i-1][0][1] * 8 % mod;
f[i][0][0] %= mod;
f[i][0][1] = (f[i-1][0][0] + f[i-1][0][1]) % mod;
f[i][1][0] = (ll) f[i-1][1][0] * 9 % mod;
f[i][1][0] += (ll) f[i-1][1][1] * 8 % mod;
f[i][1][0] %= mod;
f[i][1][1] = (f[i-1][1][0] + f[i-1][1][1]) % mod;
}
root = new node(1,N);
//~ int ans = 0;
//~ FOR(x,0,1) FOR(y,0,1) {
//~ ans += f[N][x][y];
//~ cout << f[N][x][y] << ' ';
//~ }
//~ cout << " :: " << ans << endl;
answer(1,N);
FOR(i,1,Q){
int T; cin >> T;
if (T == 1) {
int L, R; cin >> L >> R;
//~ TRACE(T _ L _ R);
answer(L,R);
} else {
int P; char D; cin >> P >> D;
root->update(P,D);
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
1792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
1792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
