Guest User

Solution to ARJN

a guest
Jun 18th, 2019
27
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //bluishgreen
  2. #pragma GCC optimize("-O3")
  3. #include <bits/stdc++.h>
  4. #include <sstream>
  5. #include<ctime>
  6. using namespace std;
  7. #define REP(i,a,b) for(i=a;i!=b;i++)
  8. #define getarr(a,n) for(i=0;i<n;i++){cin>>a[i];}
  9. #define disparr(a,n) for(i=0;i<n;i++){cout<<a[i];}cout<<"\n";
  10. #define disparrs(a,n) for(i=0;i<n;i++){cout<<a[i]<<" ";}cout<<"\n";
  11. #define disparrl(a,n) for(i=0;i<n;i++){cout<<a[i]<<"\n";}cout<<"\n";
  12. #define mem0(a) memset(a,0,sizeof(a));
  13. #define ll long long int
  14. #define ld long double
  15. #define key pair<ld,ld>
  16. #define pll pair<ll,ll>
  17. #define pii pair<int,int>
  18. #define si set<int>
  19. #define vii vector<pair<int,int> >
  20. #define vi vector<int>
  21. #define vll vector<ll>
  22. #define vb vector<bool>
  23. #define vvi vector<vector<int>>
  24. #define vs vector<string>
  25. #define all(v) v.begin(),v.end()
  26. #define pb push_back
  27. #define pob pop_back
  28. #define pof pop_front
  29. #define mp make_pair
  30. #define F first
  31. #define S second
  32. #define M 1000000007
  33. #define mul(x,y) ((ll)(x)*(y))%M
  34. #define tr(c,i) for(auto i = (c).begin(); i != (c).end(); i++)
  35. #define fastio  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
  36. #define INF 0x3f3f3f3f
  37. int MOD(int a, int b)
  38. {
  39.     if(a>b)
  40.     return a-b;
  41.     else
  42.     return b-a;
  43. }
  44. ll max3(ll a,ll b,ll c)
  45. {
  46.     return max(c,max(a,b));
  47. }
  48. ll power(ll x,ll y, ll p)
  49. {
  50.     ll res = 1;
  51.     x = x % p;
  52.     while (y > 0)
  53.     {
  54.         if (y & 1)
  55.             res = (res*x) % p;
  56.         y = y>>1;
  57.         x = (x*x) % p;
  58.     }
  59.     return res;
  60. }
  61. ll max(ll a,ll b)
  62. {
  63.     return (a>b)?a:b;
  64. }
  65. ll min(ll a,ll b)
  66. {
  67.     return (a<b)?a:b;
  68. }
  69. ll gcd(ll a,ll b)
  70. {
  71.     if(b==0)
  72.         return a;
  73.     else
  74.         return gcd(b,a%b);
  75. }
  76. ll gcd_ext(ll a,ll b,ll &x, ll &y)//solves a*x+b*y=gcd(a,b)
  77. {
  78.     if(b==0)
  79.     {
  80.         x=1;
  81.         y=0;
  82.         return a;
  83.     }
  84.     else
  85.     {
  86.         ll tmp,x1,y1;
  87.         tmp = gcd_ext(b,a%b,x1,y1);//stores the result to b*x1+(a%b)*y1=gcd(b,a%b)=gcd(a,b)
  88.         x = y1;
  89.         y = x1 - (a/b)*y1;
  90.         return tmp;
  91.     }
  92. }
  93. class Solution {
  94.     private:
  95.         int nPr[11][11];
  96.         int permute(int n,int r)
  97.         {
  98.             if(n < 0)
  99.                 return 0;
  100.             return nPr[n][r];
  101.         }
  102.  
  103.     public:
  104.         Solution()
  105.         {
  106.             /*We precompute the values of nPr using dp,making use of the property:
  107.             P(n,r) = P(n-1,r) + r * P(n-1,r-1).
  108.             This is quite easy to derive and prove.*/
  109.             int i,j;
  110.             for(i = 0;i <= 10;i++)
  111.             {
  112.                 for(j = 0;j <= 10;j++)
  113.                 {
  114.                     if(j == 0)
  115.                         nPr[i][j] = 1;//base case
  116.                     else if(i < j)
  117.                         nPr[i][j] = 0;
  118.                     else
  119.                     {
  120.                         nPr[i][j] = nPr[i-1][j]+ j * nPr[i-1][j-1];
  121.                     }
  122.                 }
  123.             }
  124.         }
  125.  
  126.         int numDupDigitsAtMostN(int N)
  127.         {
  128.             //This function computes f(N) as described in the editorial.
  129.             if(N == 0 || N == 1)
  130.                 return  0;//base case
  131.             int i,j;
  132.             string a = to_string(N);//converting the number to a string makes processing easier.
  133.             int ans = N;
  134.             int n = a.size();//length of the number
  135.             map<char,int> m;///this map is used to check if N itself can be used in the count.
  136.             for(auto it: a)
  137.                 m[it]++;
  138.             if(m.size() == n)
  139.                 ans--;//if the number N itself has no repeated digits, subtract it.
  140.             map<char,bool> m1;//m1 stores the original digits appearing in the positions 0,1,...i-1 at the ith iteration.
  141.             for(i = 0;i < n; i++)
  142.             {
  143.                 int len = n-i-1;
  144.                 map<char,bool> av;//stores the set of available digits to be used in the positions ahead of i.
  145.                 for(j  = 0;j < 10;j++)
  146.                     av[(char)(j+48)] = true;//initially add all digits to the map.
  147.                 for(auto it: m1)
  148.                     av.erase(it.first);
  149.                 int x = av.size();  //this is the number of numbers that can be used in positons (i+1,...n-1).
  150.                 for(j = a[i];j <= 57;j++)
  151.                     av.erase(j);//remove those digits that are greater than or equal to the current digit.
  152.                
  153.                 // av now contains those digits that can be used at the current position.
  154.                 if(m1.size() == i)//no repeated digits already exist in previous indices, thus proceed to reduce the value of ans.
  155.                 {
  156.                     for(auto it: av)
  157.                     {
  158.                         if(i == 0 && it.first == 48)
  159.                         {
  160.                             /*This is the special case where the most significant digit of the number is 0. The proof of the formula
  161.                             being used here is left an an exercise for the reader.*/
  162.                             for(j = 1; j <= len; j++)
  163.                                 ans -= permute(x,j) - permute(x-1,j-1);
  164.                         }
  165.                         else
  166.                             ans -= permute(x-1,len);
  167.                     }
  168.                 }
  169.                 m1[a[i]] = true;
  170.             }
  171.             return ans;
  172.         }
  173. };
  174. int main()
  175. {
  176.     fastio;
  177.     int t;
  178.     cin>>t;
  179.     Solution* obj = new Solution();
  180.     while(t--)
  181.     {
  182.         int a,b;
  183.         cin>>a>>b;
  184.         int ans = obj->numDupDigitsAtMostN(b) - obj->numDupDigitsAtMostN(a-1);
  185.         cout<<ans<<'\n';
  186.     }
  187.     return 0;
  188. }
RAW Paste Data