QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#331359 | #1372. Rainbow Numbers | nocriz# | AC ✓ | 16ms | 3940kb | C++20 | 2.0kb | 2024-02-18 06:21:04 | 2024-02-18 06:21:04 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<long long> vi;
typedef vector<vi> vvi;
int MOD = 998244353;
vvi dp;
ll qexp(ll b, ll e) {
ll ans = 1;
for(; e > 0; e >>= 1, b = b * b % MOD) {
if(e & 1) ans = ans * b % MOD;
}
return ans;
}
ll solve(string& s, int idx, char last) {
ll ans = 0;
if(idx >= (int) s.length()) return 1;
if(last != '0' && s[idx] != '0') {
ans = (ans + (qexp(9, s.length() - idx) - 1 + MOD) % MOD * qexp(8, MOD - 2) % MOD) % MOD;
if(last != '9' + 1) ans = (ans - 1 + MOD) %MOD;
}
// cout << idx << " " << ans << "\n";
for(int i = '1'; i < s[idx]; i++) {
if(last == i) continue;
ans = (ans + qexp(9, s.length() - idx - 1)) % MOD;
}
if(last != s[idx]) ans = (ans + solve(s, idx + 1,( s[idx] == '0' && last == '9' + 1 )? '9' + 1 : s[idx])) % MOD;
// cout << s << " " << idx << " " << last << " " << ans << "\n";
return ans;
}
ll solve_everule(string &s){
int n = s.size();
ll ans = 0;
bool is_valid = 1;
for(int i=0;i+1<n;i++){
if(i > 0 && s[i] == s[i-1]){
is_valid = 0;
break;
}
ans += qexp(9, n - i - 2) * (s[i+1] - '0' - (s[i] < s[i+1]));
}
is_valid &= (s[n-1] != s[n-2]);
ans += (s[0] - '1') * qexp(9, n - 1);
for(int k=1;k<n;k++){
ans += qexp(9, n - k);
}
ans += is_valid;
ans %= MOD;
return ans;
}
void solve() {
string L, U; cin >> L >> U;
ll ans = 1;
int i = 0;
for(; i < (int) L.length() - 1 && L[i] == '0'; i++) {}
for(;i < (int) L.length() - 1; i++) {
if(L[i] == L[i + 1]) {
ans = 0;
break;
}
}
ans = (ans + solve_everule(U)) % MOD;
// cout << ans << "\n";
ans = (ans - solve_everule(L) + MOD) % MOD;
cout << ans << "\n";
}
int main() {
ios_base::sync_with_stdio(); cin.tie(0);
int T = 1;
//cin >> T;
while(T--) {
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3628kb
input:
3 65
output:
58
result:
ok single line: '58'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
37 524
output:
403
result:
ok single line: '403'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
974 9522
output:
6271
result:
ok single line: '6271'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
50518 71177
output:
13592
result:
ok single line: '13592'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
31718 829025
output:
477007
result:
ok single line: '477007'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
2673659 3522358
output:
444961
result:
ok single line: '444961'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
68790054 74835016
output:
3158763
result:
ok single line: '3158763'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
17596932 830146213
output:
355204747
result:
ok single line: '355204747'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
4559302681 8460113494
output:
551444164
result:
ok single line: '551444164'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
69096117055 78607961801
output:
325094872
result:
ok single line: '325094872'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
73724561911 889698372081
output:
41274511
result:
ok single line: '41274511'
Test #12:
score: 0
Accepted
time: 9ms
memory: 3940kb
input:
394508574650091022512909571921114492507182694804026914557940803351210811949294279029752773817948937368669076640956044457423812581727430884005816206959427698347341885326394187628757727906699306514383875164462186324492548299764354798393930933304229249368412800790454859889329435645073095955728789171702...
output:
756013076
result:
ok single line: '756013076'
Test #13:
score: 0
Accepted
time: 7ms
memory: 3696kb
input:
422014715369079097925608576097053393447341302972956361410316610182985064145389774113205524523087296205181295465843585593935732826938976987802078878325619776564276368817692500878159975485238243080947879152156568498810626499536300978108439515929336284446557185830049933423981614786282183661906272862517...
output:
910290565
result:
ok single line: '910290565'
Test #14:
score: 0
Accepted
time: 8ms
memory: 3620kb
input:
629396096057468187536008660523981385068079952319349471675185632997043167437177453007637825175211086119803071189551537498462585481009493935144671873254853670403033132984991648864417820658966727747779525379302774945537232349542662015587544507173985564040097599634973358738856506578728656284970453992909...
output:
206648751
result:
ok single line: '206648751'
Test #15:
score: 0
Accepted
time: 16ms
memory: 3736kb
input:
199626343357951152976038386589371212733444160365124954296963099284660388005029305337631801634925234172185609304248376473380083105406411526104699402946739597346435624847786625103712052504238131893994452042122278321653786103152589778095076110445791863192424539886648381508796263443067972336469068586450...
output:
718053737
result:
ok single line: '718053737'
Test #16:
score: 0
Accepted
time: 8ms
memory: 3676kb
input:
416808467195722010717127833402137108329359612596927289691425470111656493652261905429087663641343249238712155727095465434341074450710321551466047302616559139335310175711953306158251471371425473739854879886873588044584832688470163949674325274969568377528513249445556658110466623454653717769390783039308...
output:
182246952
result:
ok single line: '182246952'
Test #17:
score: 0
Accepted
time: 16ms
memory: 3776kb
input:
123343027257017651518445188954611335922116205762639210047994511861224460368751657727094916366693982441252856763608738504776743932824426227912514755331398286427843785571450458430865025310462426643461359293139384334713525243669047961510996307364053779014126345116040064878119666567405582997008526481779...
output:
635917051
result:
ok single line: '635917051'
Test #18:
score: 0
Accepted
time: 11ms
memory: 3680kb
input:
555447303587984935082102315240572317427032365494842712316690651708012590452140846568605875046914403037659471823547090546652528677148568592178117915826208879342008567398432355062521103014413587212424186325363147338980680164777568474515738920096377955187197462657654532855548271944324696377703605930926...
output:
609877234
result:
ok single line: '609877234'
Test #19:
score: 0
Accepted
time: 4ms
memory: 3688kb
input:
346936986726555509250989806448369042413425814612507036715378765301213065566598275883962847974103750963496684004841771015308222144469853044247988854848255290418003505127692437063318505453103279396876102565651692643033740443939691521078223172329110270567092570987328376283086698808515395858671126318600...
output:
140021677
result:
ok single line: '140021677'