题解 | #连续子数组数量#

class Solution {
public:
    int mod = 1e9 + 7;
    int n = 0;
    void func(vector<int>& a, vector<vector<int>>& arr) {
        for (int i = 0; i < n; ++i) {
            int temp = a[i];
            while (temp > 0 && temp % 2 == 0) {
                arr[i][0]++;
                temp /= 2;
            }
            temp = a[i];
            while (temp > 0 && temp % 5 == 0) {
                arr[i][1]++;
                temp /= 5;
            }
        }
    }
    int get_ans(vector<vector<int>>& arr, int x) {
        long long ans = 0;
        int two_num = 0, five_num = 0;
        int l = 0, r = 0;
        while (r < n) {
            two_num += arr[r][0];
            five_num += arr[r][1];
            while (min(two_num, five_num) >= x) {
                ans += n - r;
                two_num -= arr[l][0];
                five_num -= arr[l][1];
                ++l;
            }
            ++r;
        }
        return ans % mod;
    }
    int getSubarrayNum(vector<int>& a, int x) {
        n = a.size();
        vector<vector<int>> arr(n, vector<int> (2));
        func(a, arr);
        return get_ans(arr, x);
    }
};

乘积末尾0的数量取决于乘积中因子2和因子5的最小值。 所以，要解决这个问题，我们可以先计算一下每个元素包含几个因子2和因子5，并用一个数组arr记录下来。 之后，再用双指针遍历arr数组，当累计的因子数量中的较小值大于等于x时，连续子数组乘积末尾0的数量必然大于等于x，此时进行下标计算即可求出以指针l为起始位置的所有连续子数组的数量。