Advertisement
Guest User

Untitled

a guest
Nov 21st, 2019
102
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.24 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. ll MAX = 1e15;
  5.  
  6. long long P(int k){
  7. if (k==1) return 9;
  8.  ll dp[k][100];
  9.     for(ll i=0; i<k ; i++){
  10.         for(ll j=0; j<100; j++){
  11.               dp[i][j]=0;
  12.           }
  13.     }
  14.    for (int i=1;i<10;i++) dp[0][i]=1;
  15.  
  16.    for (int t=1;t<k;t++)
  17.      for (int i=0;i<100;i++)
  18.         for (int j=0;j<10;j++) {
  19.           if (i%10==j) continue;
  20.           if (i/10==j  && (j>0 || t!=1) ) continue;
  21.           int z=(i%10)*10+j;
  22.           dp[t][z]+=dp[t-1][i];
  23.    }
  24.   long long ans=0;
  25.   for (int i=0;i<100;i++)
  26.     ans+=dp[k-1][i];
  27.  
  28.   return ans;
  29. }
  30.  
  31.  
  32. ll f(ll x){
  33.  
  34.     if(x<10) return x;
  35.     vector<ll> nums;
  36.  
  37.     while(x>0){
  38.         nums.push_back(x%10);
  39.         x/=10;
  40.     }
  41.     reverse(nums.begin(), nums.end());
  42.     ll len = nums.size();
  43.  
  44.    long long ans=0;
  45.    for (int i=1;i<len;i++)
  46.      {
  47.          ans+=P(i);
  48.      }
  49.  
  50.     ll dp[len][100][3];
  51.     for(ll i=0; i<len ; i++){
  52.         for(ll j=0; j<100; j++){
  53.             for(ll c=0; c<3; c++){
  54.                 dp[i][j][c]=0;
  55.             }
  56.         }
  57.     }
  58.     for(ll i=1; i<10; i++){
  59.         if(nums[0]>i){
  60.             dp[0][i][0]=1;
  61.         }
  62.         else if(nums[0]==i){
  63.             dp[0][i][1]=1;
  64.         }
  65.        
  66.     }
  67.     for(ll l=0; l<len-1; l++){
  68.         for(ll i=0; i<100; i++){
  69.                 for(ll j=0; j<10; j++){
  70.                    
  71.                     if(i%10==j ) continue;
  72.  
  73.                     if(i/10==j  && (j>0 || l>0) ){
  74.                         continue;
  75.                     }
  76.                     ll k = (i%10)*10+j;
  77.  
  78.                     dp[l+1][k][0]+=dp[l][i][0];
  79.                     if(nums[l+1]==j ){
  80.                         dp[l+1][k][1]+=dp[l][i][1];
  81.                     }
  82.                     else if(nums[l+1]>j ) {
  83.                         dp[l+1][k][0]+=dp[l][i][1];
  84.                     }
  85.                  }
  86.  
  87.         }
  88.     }
  89.     for(ll i=0; i<100; i++){
  90.         ans+=dp[len-1][i][0];
  91.         ans+=dp[len-1][i][1];
  92.     }
  93.     return ans;
  94. }
  95.  
  96. int main(){
  97.     freopen("numbers.in", "r", stdin);
  98.     freopen("numbers.out", "w", stdout);
  99.     ios_base::sync_with_stdio(0);
  100.  
  101.     ll a1, a2;
  102.     cin >> a1 >> a2;
  103.  
  104.  
  105.     cout << f(a2)-f(a1-1);
  106.  
  107.     return 0;
  108. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement