QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#584152 | #8337. Counter Reset Problem | cwfxlh | TL | 9ms | 3860kb | C++14 | 2.0kb | 2024-09-23 09:25:28 | 2024-09-23 09:25:28 |
Judging History
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...