제출 #318171

#제출 시각아이디문제언어결과실행 시간메모리
318171DymoPalindrome-Free Numbers (BOI13_numbers)C++14
100 / 100
4 ms4236 KiB
#include<bits/stdc++.h>

using namespace std;


#define pb    push_back
#define eb   emplace_back
#define ll  long long
#define pll pair<ll,ll>
#define ff first
#define ss second
//#define endl "\n"
const ll maxn=1e6+50;
const ll mod =998244353 ;
const ll base=3e18;

ll dp[50][20][20][5][5];

ll b[maxn];
ll cnt1;
ll dem(ll p)
{
   ll cnt=0;
   while (p)
   {
       cnt++;
       p/=10;
   }
   return cnt;
}
ll dem1=0;
ll dosth(ll id,ll nw1,ll nw2,ll h,ll dd)
{


    if (dp[id][nw1][nw2][h][dd]!=-1)
    {
       return dp[id][nw1][nw2][h][dd];
    }
     if (id==cnt1) return dp[id][nw1][nw2][h][dd]=1;
    ll t=0;
    if (dd==0)
    {
        t=t+dosth(id+1,10,10,1,0);
    }
    for (int i=0;i<=9;i++)
    {
        if (dd==0&&i==0) continue;
        if (!h&&b[id+1]<i) continue;
        if (i==nw1||i==nw2) continue;
        t=t+dosth(id+1,nw2,i,h|(b[id+1]>i),1);
    }
    return dp[id][nw1][nw2][h][dd]=t;


}
ll cntpp(ll a)
{
    if (a<0) return 0;

    cnt1 =dem(a);
    ll h= cnt1;
    memset(dp,-1,sizeof(dp));
    while (a)
    {
        b[h]=(a%10);
        a/=10;
        h--;
    }

    /*for (int i=1;i<=cnt1;i++)
    {
        cout <<b[i]<<endl;
    }*/
    return dosth(0,10,10,0,0);

}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    /*if (fopen("p.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }*/
    ll a, b;
    cin>> a>> b;
     cout <<cntpp(b)-cntpp(a-1);
    //  cout <<cntpp(a)<<endl;





}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...