QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#348292#8337. Counter Reset Problemucup-team346#TL 19ms85952kbC++141.9kb2024-03-09 17:45:412024-03-09 17:45:42

Judging History

你现在查看的是最新测评结果

  • [2024-03-09 17:45:42]
  • 评测
  • 测评结果:TL
  • 用时:19ms
  • 内存:85952kb
  • [2024-03-09 17:45:41]
  • 提交

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...

output:


result: