QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#584152#8337. Counter Reset ProblemcwfxlhTL 9ms3860kbC++142.0kb2024-09-23 09:25:282024-09-23 09:25:28

Judging History

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

  • [2024-09-23 09:25:28]
  • 评测
  • 测评结果:TL
  • 用时:9ms
  • 内存:3860kb
  • [2024-09-23 09:25:28]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define MOD 1000000009
using namespace std;
int n,a[5003],ans,dp[5003][(1<<10)][2],f[13],g[13],k1,k2,k3,k4;
string s;
int getv(){
    int ret=0;
    for(int i=0;i<=9;i++)if(g[i]!=g[i+1])ret+=(1<<i);
    return ret;
}
int fstp(int X,int Y){
    int ret=1,bse=X;
    while(Y){
        if(Y%2)ret=ret*bse%MOD;
        bse=bse*bse%MOD;
        Y/=2;
    }
    return ret;
}
int calc(){
    dp[0][0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<(1<<10);j++)dp[i][j][0]=dp[i][j][1]=0;
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<(1<<10);j++){
            for(int u=0;u<=9;u++)f[u]=((j&(1<<u))!=0);
            for(int u=9;u>=0;u--)f[u]+=f[u+1];
            for(int u=0;u<=9;u++){
                for(int o=0;o<=9;o++){
                    if(o<=u)g[o]=max(f[o],f[u+1]+1);
                    else g[o]=f[o];
                }
                k1=getv();
                dp[i+1][k1][1]=(dp[i+1][k1][1]+dp[i][j][1])%MOD;
                if(u<a[i+1])dp[i+1][k1][1]=(dp[i+1][k1][1]+dp[i][j][0])%MOD;
                if(u==a[i+1])dp[i+1][k1][0]=(dp[i+1][k1][0]+dp[i][j][0])%MOD;
            }
        }
    }
    int ret=0;
    for(int i=0;i<(1<<10);i++){
        for(int j=0;j<=9;j++)f[j]=((i&(1<<j))!=0);
        for(int j=9;j>=0;j--)f[j]+=f[j+1];
        ret=(ret+(f[1]*10ll%MOD)*(dp[n][i][0]+dp[n][i][1]))%MOD;
    }
    for(int i=0;i<a[1];i++)ret=(ret-i*fstp(10,n-1));
    k1=0;
    for(int i=1;i<=n;i++)k1=(k1*10ll+a[i])%MOD;
    k1++;
    k1=(k1-a[1]*fstp(10,n-1))%MOD;
    ret=(ret-a[1]*k1)%MOD;
    return ret;
}
signed main(){
    ios::sync_with_stdio(false);
    cin>>n;
    cin>>s;
    for(int i=1;i<=n;i++)a[i]=s[i-1]-'0';
    a[n]--;
    for(int i=n;i;i--){
        if(a[i]<0){
            a[i-1]--;
            a[i]+=10;
        }
    }
    if(a[0]>=0)ans=(ans-calc())%MOD;
    cin>>s;
    for(int i=1;i<=n;i++)a[i]=s[i-1]-'0';
    ans=(ans+calc())%MOD;
    ans%=MOD;
    ans+=MOD;
    ans%=MOD;
    cout<<ans;
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 3612kb

input:

2
19 23

output:

51

result:

ok 1 number(s): "51"

Test #2:

score: 0
Accepted
time: 7ms
memory: 3700kb

input:

6
100084 518118

output:

9159739

result:

ok 1 number(s): "9159739"

Test #3:

score: 0
Accepted
time: 9ms
memory: 3860kb

input:

12
040139021316 234700825190

output:

771011551

result:

ok 1 number(s): "771011551"

Test #4:

score: 0
Accepted
time: 2ms
memory: 3672kb

input:

1
5 6

output:

9

result:

ok 1 number(s): "9"

Test #5:

score: 0
Accepted
time: 2ms
memory: 3620kb

input:

2
06 72

output:

609

result:

ok 1 number(s): "609"

Test #6:

score: 0
Accepted
time: 3ms
memory: 3708kb

input:

3
418 639

output:

2912

result:

ok 1 number(s): "2912"

Test #7:

score: -100
Time Limit Exceeded

input:

5000
0517031462295902016787205636287842713710486158285091634061538907131690102542613263904109051429895599547551249682345434244517372300211330243052548402051817254239088411128320032011447373157210750522722463984933692575118884942425236057310901139962840332684448050855646476051878413350560455871387882...

output:


result: