QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#350645 | #8337. Counter Reset Problem | grass8cow | WA | 2ms | 10176kb | C++17 | 1.2kb | 2024-03-10 22:32:36 | 2024-03-10 22:32:38 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n;
const int mod=998244353;
char c[5010];
int a[5010];
int dp[5010][512][2],pp[512],to[512][10];
bool fl[5010][512][2];
int dfs(int x,int e,int z){
if(x==n)return pp[e];
if(fl[x][e][z])return dp[x][e][z];
int ans=0;
for(int i=0;i<=(z?9:a[x]);i++)
(ans+=dfs(x+1,to[e][i],z||(i<a[x])))%=mod;
fl[x][e][z]=1;
return dp[x][e][z]=ans;
}
int doi(){
memset(fl,0,sizeof(fl));
int ans=10ll*dfs(0,0,0)%mod,e=0,P=1;
for(int i=1;i<n;i++)e=(10ll*e%mod+a[i])%mod,P=10ll*P%mod;
e++;
for(int i=0;i<=a[0];i++)(ans-=1ll*((i==a[0])?e:P)*i%mod)%=mod;
return ans;
}
int main(){
for(int s=0;s<512;s++){
if(s)pp[s]=pp[s>>1]+(s&1);
for(int i=0;i<10;i++){
if(i==0)to[s][i]=s;
else{
//替换掉第一个<=i的
to[s][i]=s^(1<<(i-1));
for(int j=i-1;j>=0;j--)if((s>>j)&1){
to[s][i]^=(1<<j);
break;
}
}
}
}
scanf("%d%s",&n,c);
for(int i=0;i<n;i++)a[i]=c[i]-'0';
a[n-1]--;
int o=n-1;
while(o>0&&a[o]<0)a[o]+=10,a[o-1]--;
int ans=0;
if(a[0]>=0)ans=mod-doi();
scanf("%s",c);
for(int i=0;i<n;i++)a[i]=c[i]-'0';
(ans+=doi())%=mod;
return printf("%d",(ans+mod)%mod),0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 10176kb
input:
2 19 23
output:
51
result:
ok 1 number(s): "51"
Test #2:
score: 0
Accepted
time: 2ms
memory: 9660kb
input:
6 100084 518118
output:
9159739
result:
ok 1 number(s): "9159739"
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 9492kb
input:
12 040139021316 234700825190
output:
264259530
result:
wrong answer 1st numbers differ - expected: '771011551', found: '264259530'