제출 #1121317

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1121317		vjudge1	Palindrome-Free Numbers (BOI13_numbers)	C++17	100 / 100	2 ms	508 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 long long
#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)
	{
    	for(ll d3=st; d3<=10; d3++)
		{
      		if(d3!=d1 && d3!=d2)
				cvb+=rec(s, pos+1, d2, d3, 0);
    	}
  	}
	else
	{
    	ll d=s[pos]-'0'+1;
    	for(ll d3=st; d3<=d; d3++)
		{
      		if(d3!=d1 && d3!=d2)
			{
        		if(d3==d)
					cvb+=rec(s, pos+1, d2, d3, 1);
        		else
					cvb+=rec(s, pos+1, d2, d3, 0);
      		}
    	}
  	}
	return dp[pos][d1][d2][strict]=cvb;
}
/*
4x^2+2+10x-5-6x

2x^2
*/
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: 25 / 25
• Subtask 2: 75 / 75