제출 #1121213

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1121213		vjudge1	Palindrome-Free Numbers (BOI13_numbers)	C++17	42.50 / 100	1 ms	548 KiB

numbers

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define run  ios_base::sync_with_stdio(false);cin.tie(0);
 
#define ll int
#define pll pair<ll, ll>
#define ull unsigned ll
#define ld double
#define endl "\n"
#define pb push_back
#define fi first
#define se second
 
#define pi acos(-1)
#define N 4007
#define minimum -9223372036854775807
#define maximum -minimum
#define mod 1000000007
 
using namespace std;
using namespace __gnu_pbds;
template <class t>
using ordered_set=tree<t, null_type,less_equal<t>, rb_tree_tag,tree_order_statistics_node_update>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll gcd(ll a, ll b)
{
	if(b==0)
		return a;
	return gcd(b, a%b);
}

ll lcm(ll a, ll b)
{
	return a/gcd(a, b)*b;
}

bool isprime(ll n)
{
	if(n==1)
		return 0;
	for(ll i=2; i*i<=n; i++)
	{
		if(n%i==0)
			return 0;
	}
	return 1;
}

ll binpow(ll a, ll b)
{
    a%=mod;
    ll res=1;
    while(b>0)
	{
        if(b%2==1)
            res=(res*a)%mod;
        a=(a*a)%mod;
        b/=2;
    }
    return res;
}

ll dp[20][11][11][2];

ll rec(string &s, ll pos, ll d1, ll d2, ll strict)
{
	ll sz=s.length();
	if(sz==pos)
		return 1;
	if(dp[pos][d1][d2][strict]!=-1)
		return dp[pos][d1][d2][strict];
	ll cvb=0;
	if(d2==0)
		cvb+=rec(s, pos+1, d1, d2, 0);
	ll st=1;
	if(d2==0)
		st++;
	if(strict)
	{
		ll fin=s[pos]-'0'+1;
		for(ll d3=st; d3<=fin; d3++)
		{
			if(d3==d1 || d3==d2)
				continue;
			if(d3==fin)
				cvb+=rec(s, pos+1, d2, d3, 1);
        	else
				cvb+=rec(s, pos+1, d2, d3, 0);
		}
	}
	else
	{
		for(ll d3=st; d3<=10; d3++)
		{
      		if(d3!=d1 && d3!=d2)
				cvb+=rec(s, pos+1, d2, d3, 0);
    	}
	}
	return dp[pos][d1][d2][strict]=cvb;
}

ll prnt(ll n)
{
	if(n<0)
		return 0;
	string s=to_string(n);
	for(ll i=0; i<20; i++) 
	{
	   	for(ll d1=0; d1<=10; d1++) 
		{
	   		for(ll d2=0; d2<=10; d2++) 
			{
	       		dp[i][d1][d2][0]=-1;
	       		dp[i][d1][d2][1]=-1;
	   		}
	   	}
	}
	return rec(s, 0, 0, 0, 1);
}

int main()
{
	run;
	ll a, b;
	cin>>a>>b;
	cout<<prnt(b)-prnt(a-1)<<endl;
}
// By Xanlar

• Subtask 1: 22.5 / 25
• Subtask 2: 20 / 75