QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#350645#8337. Counter Reset Problemgrass8cowWA 2ms10176kbC++171.2kb2024-03-10 22:32:362024-03-10 22:32:38

Judging History

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

  • [2024-03-10 22:32:38]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:10176kb
  • [2024-03-10 22:32:36]
  • 提交

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'