Math Them problem

#1

I am not able to understand the editorial please explain it in short .This question is under DP with Bitmasking but the constraints are too large for DP with Bitmasking.
In the Editorial I thing something like binary search is done …Please explain the Editorial.

#2

Yeah the question doesn’t use bitmasking but instead has a very interesting approach.
The dp part is precalculation of the prefix sums for each digit at every index i.

    F(i,0,n-1)
    {
        cnt[i][x[i]-'0']++;
        if(i>=1)
        {
            F(j,0,9)
                cnt[i][j] += cnt[i-1][j];
        }
    }

and hass is the required amount

    F(i,0,m-1)
    {
        ll y;
        cin>>y;
        hass[y]++;
    }

Now the idea to solve is that ,for every index i ,find the closest index j,(j>=i), such that this range contains all the digits present in hass atleast once. So this can be done using prefix sums we precalculated.

            F(j,0,9)
            {
                if(i>=1)
                {
                    if(hass[j] > cnt[mid][j]-cnt[i-1][j])
                        check = 0;
                }
                else
                {
                    if(hass[j] > cnt[mid][j])
                        check = 0;
                }
            }

Now if you are familiar with how binary search works, we can find this j in log(n) time using binary search.
Once you find this j you are supposed to add the number of substrings starting from i which follow the property, so that would be simply

        if(id!=-1)
        {
            ans += (n-id);
        }

So the complexity of the solution is O(Nlog(N)*10)