数位dp全WA
查看原帖
数位dp全WA
800543
NirvanaCeleste楼主2024/7/23 11:17
#include <bits/stdc++.h>
using namespace std;
long long a,b,tota,totb;
int num1[14],num2[14];
long long tenjc[15],num[15],zero[15],ans1[15],ans2[15];
void init(){
	tenjc[0] = 1;
	for(int i=1;i<=13;i++) tenjc[i] = tenjc[i-1] * 10,num[i] = num[i-1] * 10 + tenjc[i-1];
	zero[1] = 1;
	for(int i=2;i<=13;i++) zero[i] = zero[i-1] + tenjc[i-1];
	return;
}
void slove(long long x,long long y){
	while(x) num1[++tota] = x%10,x/=10;
	while(y) num2[++totb] = y%10,y/=10;//倒序存储 
	for(int i=tota;i>=1;i--){
		for(int j=0;j<=num1[i];j++) ans1[j] += tenjc[i-1];
		for(int k=0;k<=9;k++) ans1[k] += num[i-1] * num1[i];
	}
	ans1[0] -= zero[tota];	
	for(int i=totb;i>=1;i--){
		for(int j=0;j<=num2[i];j++) ans2[j] += tenjc[i-1];
		for(int k=0;k<=9;k++) ans2[k] += num[i-1] * num2[i];
	}
	ans2[0] -= zero[totb];
	return;
}
int main(){
	cin>>a>>b;
	init();
	slove(a-1,b);
//	for(int i=0;i<=9;i++) cout<<ans1[i]<<" ";
//	cout<<endl;
//	for(int i=0;i<=9;i++) cout<<ans2[i]<<" ";
//	cout<<endl;
	for(int i=0;i<=9;i++) cout<<ans2[i] - ans1[i]<<" ";
	return 0;
}
2024/7/23 11:17
加载中...