有多组输入数据.给出一个长度为 n的序列a,求满足如下条件连续字段的数量.令x = al * al+1 * al+2 * ... * ar.那么x的末尾恰好有k个零。再优化一下复杂度, C++代码

可以使用前缀积和二分查找来解决这个问题。

具体来说，我们可以先用前缀积计算出任意一段区间的积，然后对于每个右端点 r，通过二分查找找到最小的左端点 l，使得 al * al+1 * ... * ar 末尾恰好有 k 个零。这个过程中，我们可以通过统计二分查找的结果数量来得到满足条件的连续字段的数量。

具体实现如下：

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 5;
int a[MAXN], pre[MAXN];

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        pre[i] = pre[i - 1] + (a[i] == 5);
    }
    long long ans = 0;
    for (int r = 1; r <= n; r++) {
        int L = 0, R = r, res = -1;
        while (L <= R) {
            int mid = (L + R) >> 1;
            if (pre[r] - pre[mid - 1] == k) {
                res = mid;
                R = mid - 1;
            } else if (pre[r] - pre[mid - 1] > k) {
                L = mid + 1;
            } else {
                R = mid - 1;
            }
        }
        if (res != -1) {
            ans += r - res + 1;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

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