给出一个长度为 n(1≤n≤2⋅10 5 ) 的序列 a (1≤a i ​ ≤10 9 )，并且保证序列 a 所有元素乘积 ≤10 18 ，求这个序列中满足如下条件的连续子段 [a l ​ …a r ​ ] 的数量： 令 x=a l ​ ⋅a l+1 ​ ⋅a l+2 ​ …a r ​ ，那么 x 的末尾恰好有 k(0≤k≤10 9 ) 个零

这是一个比较经典的问题，可以使用前缀积+二分的方法解决。

具体来说，我们可以先求出序列 a 的前缀积数组 prefix，即 prefix[i] 表示前 i 个数的乘积。然后对于每个右端点 r，我们可以二分出最小的左端点 l，使得 prefix[r]/prefix[l-1] 的末尾有 k 个零。这个二分的过程可以先二分出 prefix[r] 除以 2 的幂次，再二分出 prefix[r] 除以 5 的幂次，最后求出这两个幂次的较小值。

时间复杂度为 O(n log n)。

以下是用 C++ 实现的代码：

#include <iostream>
#include <vector>
using namespace std;

typedef long long LL;

const int MAXN = 2e5 + 5;

int n, k, ans;
vector<int> pos[MAXN];
LL a[MAXN], prefix[MAXN];

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        prefix[i] = prefix[i - 1] + a[i];
    }
    pos[0].push_back(0);
    for (int i = 1; i <= n; i++) {
        int cnt2 = 0, cnt5 = 0;
        LL tmp = prefix[i];
        while (tmp % 2 == 0) tmp /= 2, cnt2++;
        while (tmp % 5 == 0) tmp /= 5, cnt5++;
        if (cnt2 >= k) ans++; // 整个前缀和都满足要求
        if (cnt2 >= k || cnt5 >= k) {
            int target = cnt2 >= k ? cnt2 - k : 0;
            for (int j : pos[target]) {
                if (j < i) ans++; // 子区间满足要求
            }
            pos[cnt2].push_back(i);
        }
    }
    cout << ans << endl;
    return 0;
}

其中 pos[i] 表示前缀和中末尾有 i 个 0 的位置的集合。我们遍历前缀和数组 prefix，对于每个位置 i，我们计算出 prefix[i] 末尾的 2 的幂次和 5 的幂次，分别记为 cnt2 和 cnt5。如果 cnt2 大于等于 k，则整个前缀和都满足要求，因此可以直接将 ans 加 1。如果 cnt2 小于 k 且 cnt5 小于 k，则该前缀和不满足要求，不需要做任何处理。如果 cnt2 大于等于 k 或 cnt5 大于等于 k，则我们需要找到前缀和中末尾恰好有 cnt2 - k 或 cnt5 - k 个 0 的位置 j，然后对于每个位置 j，子区间 [j+1, i] 的乘积末尾恰好有 k 个 0，因此可以将 ans 加上 j 的个数。最后，我们将位置 i 加入 pos[cnt2] 中，以便后续计算。

时间复杂度为 O(n log n)。