Dang_Quan_10_Tin

COMNUM

Sep 22nd, 2021 (edited)
572
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define task "COMNUM"
  2.  
  3. #include <iostream>
  4. #include <cstdio>
  5. #include <algorithm>
  6. #include <cstring>
  7. #include <iomanip>
  8. #include <vector>
  9. #include <cmath>
  10.  
  11. using namespace std;
  12.  
  13. using ll = long long;
  14. using ld = long double;
  15.  
  16. constexpr int N = 1e5 + 5;
  17.  
  18. using Integer = ll;
  19.  
  20. string l, r;
  21.  
  22. void Read()
  23. {
  24.     cin >> l >> r;
  25.  
  26.     reverse(l.begin(), l.end());
  27.     while (l.size() < r.size())
  28.         l.push_back('0');
  29.     reverse(l.begin(), l.end());
  30. }
  31.  
  32. /*Subtask 1*/
  33.  
  34. ll toLL(const string &s)
  35. {
  36.     ll ans(0);
  37.     for (auto i : s)
  38.         ans = ans * 10 + i - '0';
  39.     return ans;
  40. }
  41.  
  42. ll Get(ll v)
  43. {
  44.     ll ans(1);
  45.     while (v)
  46.     {
  47.         ans *= v % 10;
  48.         v /= 10;
  49.     }
  50.     return ans;
  51. }
  52.  
  53. void Sub_1() // Duyệt từ L đến R
  54. {
  55.     ll L = toLL(l),
  56.        R = toLL(r), ans(0);
  57.  
  58.     while (L <= R)
  59.         ans = max(ans, Get(L++));
  60.  
  61.     cout << ans;
  62. }
  63.  
  64. /*End subtask 1*/
  65.  
  66. /*Subtask 2*/
  67. ll dp[20][2][2];
  68.  
  69. // Hàm lấy giá trị của số y, chú ý nếu như chữ số ở vị trí đầu tiên (x == 0) thì coi như số đó chưa bắt đầu, nên trả về 1
  70.  
  71. inline int Get(int x, int y)
  72. {
  73.     if (y == 0)
  74.         return x == 0 ? 1 : 0;
  75.     return y;
  76. }
  77.  
  78. ll f(int i, bool gtl, bool ltr) // dp digit
  79. {
  80.  
  81.     ll &ans = dp[i][gtl][ltr];
  82.  
  83.     if (ans != -1)
  84.         return ans;
  85.  
  86.     if (i == (int)r.size())
  87.         return (ans = 1);
  88.  
  89.     ans = 0;
  90.  
  91.     for (int j = '0'; j <= '9'; ++j)
  92.         if ((gtl || j >= l[i]) && (ltr || j <= r[i]))
  93.             ans = max(ans, f(i + 1, gtl || j > l[i], ltr || j < r[i]) * Get(i, j - '0'));
  94.  
  95.     return ans;
  96. }
  97.  
  98. void Sub_2()
  99. {
  100.     memset(dp, -1, sizeof dp);
  101.     cout << f(0, 0, 0);
  102. }
  103.  
  104. /*End subtask 2*/
  105.  
  106. /*Subtask 3*/
  107.  
  108. const int M = 1e2 + 10; // Số lượng chữ số ước tính của đáp án
  109. const ll BASE = 1e7; // Hệ cơ số
  110. const int gd = log10(BASE);
  111. const int maxn = M / gd + 1; // Số phần tử của mảng
  112. struct Bignum
  113. {
  114.     int n;
  115.     ll a[maxn];
  116.     Bignum(ll x = 0)
  117.     {
  118.         memset(a, 0, sizeof a);
  119.         n = 0;
  120.         do
  121.         {
  122.             a[n++] = x % BASE;
  123.             x /= BASE;
  124.         } while (x);
  125.     }
  126.     void fix()
  127.     {
  128.         ++n;
  129.         for (int i = 0; i < n - 1; ++i)
  130.         {
  131.             a[i + 1] += a[i] / BASE;
  132.             a[i] %= BASE;
  133.             if (a[i] < 0)
  134.             {
  135.                 a[i] += BASE;
  136.                 --a[i + 1];
  137.             }
  138.         }
  139.         while (n > 1 && a[n - 1] == 0)
  140.             --n;
  141.     }
  142.     // Vì chỉ nhân với số nguyên nên có thể nhân trong O(n)
  143.     Bignum &operator*=(const ll &x)
  144.     {
  145.         for (int i = 0; i < n; ++i)
  146.             a[i] *= x;
  147.  
  148.         fix();
  149.         return *this;
  150.     }
  151.     Bignum &operator*=(const Bignum &x)
  152.     {
  153.         vector<ll> c(n + x.n);
  154.         for (int i = 0; i < n; ++i)
  155.             for (int j = 0; j < x.n; ++j)
  156.                 c[i + j] += a[i] * x.a[j];
  157.  
  158.         n += x.n - 1;
  159.  
  160.         for (int i = 0; i < n; ++i)
  161.             a[i] = c[i];
  162.  
  163.         fix();
  164.         return *this;
  165.     }
  166.     Bignum operator*(const Bignum &s)
  167.     {
  168.         Bignum c;
  169.         copy(a, a + n, c.a);
  170.         c.n = n;
  171.         c *= s;
  172.         return c;
  173.     }
  174.     bool operator<(const Bignum &s) const
  175.     {
  176.         if (n < s.n)
  177.             return true;
  178.         if (n > s.n)
  179.             return false;
  180.         for (int i = n - 1; i > -1; --i)
  181.             if (a[i] > s.a[i])
  182.                 return false;
  183.             else if (a[i] < s.a[i])
  184.                 return true;
  185.         return false;
  186.     }
  187.     friend ostream &operator<<(ostream &out, const Bignum &x)
  188.     {
  189.         int i = x.n;
  190.         while (i > 0 && x.a[i] == 0)
  191.             --i;
  192.         out << x.a[i];
  193.         for (--i; ~i; --i)
  194.             out << setw(gd) << setfill('0') << x.a[i];
  195.         return out;
  196.     }
  197. };
  198.  
  199. Bignum Pow9[M];
  200.  
  201. void Sub_3()
  202. {
  203.     int pos(0);
  204.  
  205.     for (; pos < (int)r.size() && l[pos] == r[pos]; ++pos);
  206.  
  207.     Bignum pre(1), ans(0);
  208.  
  209.     Pow9[0] = Bignum(1);
  210.     for (int i = 1; i <= (int)r.size(); ++i)
  211.     {
  212.         Pow9[i] = Pow9[i - 1];
  213.         Pow9[i] *= 9ll;
  214.         if (i <= pos)
  215.             pre *= (ll)(r[i - 1] - '0');
  216.     }
  217.  
  218.     for (int i = pos; i <= (int)r.size(); ++i)
  219.     {
  220.         Bignum temp = pre * Pow9[max(0, (int)r.size() - i - 1)];
  221.  
  222.         if (i < (int)r.size())
  223.         {
  224.             temp *= (ll)Get(i, max(0, r[i] - '0' - 1));
  225.             pre *= (ll)(r[i] - '0');
  226.         }
  227.  
  228.         if (ans < temp)
  229.             ans = temp;
  230.     }
  231.  
  232.     cout << ans;
  233. }
  234.  
  235. int32_t main()
  236. {
  237.     ios::sync_with_stdio(0);
  238.     cin.tie(0);
  239.     cout.tie(0);
  240.     freopen(task ".INP", "r", stdin);
  241.     freopen(task ".OUT", "w", stdout);
  242.     Read();
  243.     if ((int)r.size() <= 6)
  244.         Sub_1();
  245.     else if ((int)r.size() <= 18)
  246.         Sub_2();
  247.     else if ((int)r.size() <= 100)
  248.         Sub_3();
  249. }
  250.  
RAW Paste Data