C++ এ অ্যারে পুনরুদ্ধার করুন

ধরুন একটি প্রোগ্রাম আছে যা একটি অ্যারের অ্যারে উপাদানগুলি প্রিন্ট করতে ব্যবহৃত হয়, কিন্তু প্রোগ্রামটিতে সামান্য ভুল ছিল। যে প্রোগ্রামে প্রতিটি উপাদানের পরে কোন সাদা স্থান ছিল না, তাই যদি আমাদের একটি মুদ্রিত স্ট্রিং থাকে, তাহলে আমরা কি আবার অ্যারেটি পুনরায় তৈরি করতে পারি? আমরা জানি অ্যারের উপাদানগুলি 1 থেকে k এর মধ্যে।

স্ট্রিং s এবং পূর্ণসংখ্যা k দেওয়া. আমাদের খুঁজে বের করতে হবে কত সংখ্যক উপায়ে আমরা অ্যারে পুনরুদ্ধার করতে পারি। উত্তরটি খুব বড় হতে পারে তাই এটি মডিউল 10^9 + 7 ফেরত দিন।

সুতরাং, যদি ইনপুটটি S ="1318" এবং k =2000 এর মত হয়, তাহলে আউটপুট হবে 8, কারণ আমরা 8টি ভিন্ন অ্যারে তৈরি করতে পারি যেমন [1318], [131,8], [13,18], [1,318] ],[1,3,18],[1,31,8],[13,1,8],[1,3,1,8]

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• const int m =1e9 + 7

• একটি মানচিত্র ডিপি

  সংজ্ঞায়িত করুন

• একটি ফাংশন add() সংজ্ঞায়িত করুন, এটি a, b,

  লাগবে

• ফিরুন ((a mod m) + (b mod m)) mod m

• একটি ফাংশন সাহায্য() সংজ্ঞায়িত করুন, এটি idx, s, num, k,

  লাগবে

• যদি idx>=s এর আকার হয়, তাহলে −

  • রিটার্ন 1

• যদি idx dp-এ থাকে এবং num হয় dp[idx]-এ, তাহলে −

  • dp[idx, num]

    ফেরত দিন

• ret :=0

• যদি num>=1 এবং num>=k এবং s[idx] '0' এর সমান না হয়, তাহলে −

  • ret :=add(help(idx, s, 0, k), ret)

• যদি num * 10 + (s[idx] - '0') <=k, তাহলে −

  • ret :=add(help(idx + 1, s, num * 10 + (s[idx] - ASCII of '0'), k), ret)

• dp[idx, num] :=ret

• রিটার্ন রিটার্ন

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• n :=s

  এর আকার

• n + 1

  আকারের একটি অ্যারে উত্তর সংজ্ঞায়িত করুন

• উত্তর[0] :=1

• s :=s

  এর আগে একটি সাদা স্থান সংযুক্ত করুন

• ks :=k কে স্ট্রিং এ রূপান্তর করুন

• আরম্ভ করার জন্য i :=1, যখন i <=n, আপডেট করুন (i 1 দ্বারা বাড়ান), করবেন −

  • cnt :=1

  • temp :=ফাঁকা স্ট্রিং

  • আরম্ভ করার জন্য j :=i, যখন j>=1 এবং cnt <=10, আপডেট করুন (j 1 দ্বারা হ্রাস করুন), (1 দ্বারা cnt বাড়ান), করুন −

    • temp :=s[j] + temp

    • যদি s[j] '0' এর মত হয়, তাহলে −

      • নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তি এড়িয়ে যান

    • যদি temp এর সাইজ> ks এর সাইজ হয়, তাহলে −

      • লুপ থেকে বেরিয়ে আসুন

    • val :=সংখ্যা হিসাবে temp

    • যদি val>=1 এবং val <=k, তাহলে −

      • ans[i] :=add(ans[i], ans[j - 1])

• উত্তর [n]

  ফেরত দিন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int m = 1e9 + 7;
class Solution {
   public:
   unordered_map<int, unordered_map<lli, int> > dp;
   lli add(lli a, lli b){
      return ((a % m) + (b % m)) % m;
   }
   int help(int idx, string& s, lli num, int k){
      if (idx >= s.size())
      return 1;
      if (dp.count(idx) && dp[idx].count(num))
      return dp[idx][num];
      int ret = 0;
      if (num >= 1 && num <= k && s[idx] != '0') {
         ret = add(help(idx, s, 0, k), ret);
      }
      if (num * 10 + (s[idx] - '0') <= k) {
         ret = add(help(idx + 1, s, num * 10 + (s[idx] - '0'), k),
         ret);
      }
      return dp[idx][num] = ret;
   }
   int numberOfArrays(string s, int k){
      int n = s.size();
      vector<lli> ans(n + 1);
      ans[0] = 1;
      s = " " + s;
      string ks = to_string(k);
      for (lli i = 1; i <= n; i++) {
         lli cnt = 1;
         string temp = "";
         for (lli j = i; j >= 1 && cnt <= 10; j--, cnt++) {
            temp = s[j] + temp;
            if (s[j] == '0')
               continue;
            if (temp.size() > ks.size())
            break;
            lli val = stol(temp);
            if (val >= 1 && val <= k) {
               ans[i] = add(ans[i], ans[j - 1]);
            }
         }
      }
      return ans[n];
   }
};
main(){
   Solution ob;
   cout << (ob.numberOfArrays("1318",2000));
}

ইনপুট

"1318", 2000

আউটপুট

8