Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- ll MAX = 1e15;
- long long P(int k){
- if (k==1) return 9;
- ll dp[k][100];
- for(ll i=0; i<k ; i++){
- for(ll j=0; j<100; j++){
- dp[i][j]=0;
- }
- }
- for (int i=1;i<10;i++) dp[0][i]=1;
- for (int t=1;t<k;t++)
- for (int i=0;i<100;i++)
- for (int j=0;j<10;j++) {
- if (i%10==j) continue;
- if (i/10==j && (j>0 || t!=1) ) continue;
- int z=(i%10)*10+j;
- dp[t][z]+=dp[t-1][i];
- }
- long long ans=0;
- for (int i=0;i<100;i++)
- ans+=dp[k-1][i];
- return ans;
- }
- ll f(ll x){
- if(x<10) return x;
- vector<ll> nums;
- while(x>0){
- nums.push_back(x%10);
- x/=10;
- }
- reverse(nums.begin(), nums.end());
- ll len = nums.size();
- long long ans=0;
- for (int i=1;i<len;i++)
- {
- ans+=P(i);
- }
- ll dp[len][100][3];
- for(ll i=0; i<len ; i++){
- for(ll j=0; j<100; j++){
- for(ll c=0; c<3; c++){
- dp[i][j][c]=0;
- }
- }
- }
- for(ll i=1; i<10; i++){
- if(nums[0]>i){
- dp[0][i][0]=1;
- }
- else if(nums[0]==i){
- dp[0][i][1]=1;
- }
- }
- for(ll l=0; l<len-1; l++){
- for(ll i=0; i<100; i++){
- for(ll j=0; j<10; j++){
- if(i%10==j ) continue;
- if(i/10==j && (j>0 || l>0) ){
- continue;
- }
- ll k = (i%10)*10+j;
- dp[l+1][k][0]+=dp[l][i][0];
- if(nums[l+1]==j ){
- dp[l+1][k][1]+=dp[l][i][1];
- }
- else if(nums[l+1]>j ) {
- dp[l+1][k][0]+=dp[l][i][1];
- }
- }
- }
- }
- for(ll i=0; i<100; i++){
- ans+=dp[len-1][i][0];
- ans+=dp[len-1][i][1];
- }
- return ans;
- }
- int main(){
- freopen("numbers.in", "r", stdin);
- freopen("numbers.out", "w", stdout);
- ios_base::sync_with_stdio(0);
- ll a1, a2;
- cin >> a1 >> a2;
- cout << f(a2)-f(a1-1);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement