QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#348292 | #8337. Counter Reset Problem | ucup-team346# | TL | 19ms | 85952kb | C++14 | 1.9kb | 2024-03-09 17:45:41 | 2024-03-09 17:45:42 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int P = 1000000009;
void Add(int &a,int b){
a += b;
if(a >= P) a -= P;
}
int n;
int f[5005][1050][2],sum[5005][1050][2];
const int M = (1 << 10) - 1;
const int M2 = (1 << 10) - 2;
int calc(string s){
memset(f,0,sizeof(f));
memset(sum,0,sizeof(sum));
f[0][0][1] = 1;
for(int i = 1;i <= n;i ++){
for(int S = 0;S < (1 << 10);S ++){
for(int id = 0;id < 2;id ++){
for(int cur = 0;cur <= (id ? s[i] - '0' : 9);cur ++){
int val = (i == 1 ? 10 - cur : 10),T = S;
int pos = -1;
for(int j = cur;j >= 1;j --){
if((S >> j) & 1){
pos = j; break;
}
}
if(pos != -1) T = S ^ (1 << pos) ^ (1 << cur),val = 0;
else T = S ^ (1 << cur);
if(cur == 0) val = 0;
Add(f[i][T][id && cur == s[i] - '0'],f[i - 1][S][id]);
Add(sum[i][T][id && cur == s[i] - '0'],(1ll * f[i - 1][S][id] * val % P + sum[i - 1][S][id]) % P);
}
}
}
}
int ret = 0;
for(int S = 0;S < (1 << 10);S ++){
for(int id = 0;id < 2;id ++){
Add(ret,sum[n][S][id]);
}
}
return ret;
}
void solve(){
cin >> n;
string s,t;
cin >> s >> t;
s = ' ' + s; t = ' ' + t;
int fl = 1;
for(int i = 1;i <= n;i ++){
if(s[i] > '0') fl = 0;
}
if(fl) cout << calc(t) << '\n';
else{
s[n] --;
for(int i = n;i >= 1;i --){
if(s[i] < '0'){
s[i] += 10;
s[i - 1] --;
}
}
cout << (calc(t) - calc(s) + P) % P << '\n';
}
}
int main(){
ios::sync_with_stdio(false);
solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 7ms
memory: 85708kb
input:
2 19 23
output:
51
result:
ok 1 number(s): "51"
Test #2:
score: 0
Accepted
time: 11ms
memory: 85952kb
input:
6 100084 518118
output:
9159739
result:
ok 1 number(s): "9159739"
Test #3:
score: 0
Accepted
time: 19ms
memory: 85656kb
input:
12 040139021316 234700825190
output:
771011551
result:
ok 1 number(s): "771011551"
Test #4:
score: 0
Accepted
time: 7ms
memory: 85944kb
input:
1 5 6
output:
9
result:
ok 1 number(s): "9"
Test #5:
score: 0
Accepted
time: 16ms
memory: 85936kb
input:
2 06 72
output:
609
result:
ok 1 number(s): "609"
Test #6:
score: 0
Accepted
time: 7ms
memory: 85880kb
input:
3 418 639
output:
2912
result:
ok 1 number(s): "2912"
Test #7:
score: -100
Time Limit Exceeded
input:
5000 0517031462295902016787205636287842713710486158285091634061538907131690102542613263904109051429895599547551249682345434244517372300211330243052548402051817254239088411128320032011447373157210750522722463984933692575118884942425236057310901139962840332684448050855646476051878413350560455871387882...