Submission #1314090

#TimeUsernameProblemLanguageResultExecution timeMemory
1314090boclobanchatPalindrome-Free Numbers (BOI13_numbers)C++20
100 / 100
1 ms332 KiB
#include<bits/stdc++.h>
using namespace std;
long long dp[22][12][12][2],dig[22];
bool kc[22][12][12][2];
long long f(int n,int a,int b,bool ck,bool st)
{
	if(n<0) return 1;
	if(ck)
	{
		long long ans=0;
		for(int j=0;j<=dig[n];j++)
		{
			if(!st&&j==0) ans+=f(n-1,a,b,ck&(j==dig[n]),false);
			else if(j!=a&&j!=b) ans+=f(n-1,b,j,ck&(j==dig[n]),true);
		}
		return ans;
	}
	else
	{
		if(kc[n][a][b][st]) return dp[n][a][b][st];
		kc[n][a][b][st]=true;
		long long ans=0;
		for(int j=0;j<=9;j++)
		{
			if(!st&&j==0) ans+=f(n-1,a,b,false,false);
			else if(j!=a&&j!=b) ans+=f(n-1,b,j,false,true);
		}
		return dp[n][a][b][st]=ans;
	}
}
long long solve(long long val)
{
	if(val<0) return 0;
	int cnt=0;
	while(val) dig[cnt++]=val%10,val/=10;
	return f(cnt-1,11,10,true,false);
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	long long l,r;
	cin>>l>>r;
	cout<<solve(r)-solve(l-1);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...