给出一个长度为 n(1 < n < 2·105) 的序列 a(1 < a < 10，并保证序列 所有素积< 1018，求这个序列中满足如下条件的连续子段 al...ar]的数量: 令x = a·al+1·al+2 ...ar，那么x的末尾恰好有 k(0 < k<109) 个零,c++代码

以下是 C++ 代码实现：

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

const int N = 2e5 + 5;
int a[N], cnt[2][N];
long long p[N];

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        p[i] = p[i - 1] + log10(a[i]);
    }

    long long ans = 0;
    for(int i = 1; i <= n; i++) {
        int t = 0;
        while(a[i] % 5 == 0) {
            a[i] /= 5;
            t++;
        }
        cnt[0][i] = cnt[0][i - 1];
        cnt[1][i] = cnt[1][i - 1];
        cnt[t & 1][i]++;

        int l = 1, r = i;
        while(l < r) {
            int mid = (l + r) >> 1;
            if(p[i] - p[mid - 1] > k) {
                if((cnt[1][i] - cnt[1][mid - 1]) & 1) ans++;
                l = mid + 1;
            } else {
                if((cnt[0][i] - cnt[0][mid - 1]) & 1) ans++;
                l = mid;
            }
        }
        if(p[i] <= k && (cnt[0][i] & 1)) ans++;
    }
    printf("%lld\n", ans);
    return 0;
}

思路解析：

首先，对于这种求连续子段的问题，我们通常会考虑枚举右端点。对于右端点 $r$，我们需要求出有多少个左端点 $l$，使得 $a_l \times a_{l+1} \times \cdots \times a_r$ 的末尾恰好有 $k$ 个零。

假设 $x = a_l \times a_{l+1} \times \cdots \times a_r$，那么 $x$ 的末尾有多少个零，就取决于 $x$ 中有多少个因子 $5$。我们假设 $x$ 中因子 $5$ 的个数为 $u$，那么 $x$ 的末尾将有 $u$ 个零。

我们可以通过对每个数进行质因数分解，统计每个 $a_i$ 中因子 $5$ 的个数，然后用前缀和的方式统计 $x$ 中因子 $5$ 的个数 $u$。具体来说，对于一个右端点 $r$，假设 $r$ 对应的 $a_r$ 中因子 $5$ 的个数为 $t_r$，那么从 $l$ 到 $r$ 的连续子段 $a_l \times a_{l+1} \times \cdots \times a_r$ 中因子 $5$ 的个数为 $\sum_{i=l}^r t_i$。

另外，我们还需要考虑 $x$ 中因子 $2$ 的个数。在 $x$ 中，因子 $2$ 的个数比因子 $5$ 的个数多得多，所以我们只需要统计 $x$ 中因子 $5$ 的个数即可。具体来说，我们可以先对每个数进行质因数分解，然后对于每个右端点 $r$，统计前缀 $\log_{10}(a_1) + \cdots + \log_{10}(a_r)$。这个前缀和代表了 $1$ 到 $r$ 的连续子段的 $\log_{10}$ 值之和，也就是 $a_1 \times a_2 \times \cdots \times a_r$ 的 $\log_{10}$ 值。

最后，我们需要在 $l$ 到 $r$ 的区间中找到一个位置 $m$，使得 $a_l \times a_{l+1} \times \cdots \times a_m$ 的末尾恰好有 $k$ 个零，且 $m$ 尽量靠右。为了做到这一点，我们可以使用二分答案。具体来说，我们首先二分出一个位置 $m$，然后判断 $a_l \times a_{l+1} \times \cdots \times a_m$ 的末尾有多少个零。如果 $a_l \times a_{l+1} \times \cdots \times a_m$ 的末尾恰好有 $k$ 个零，那么我们就将答案加上 $1$。另外，我们还需要保证 $m$ 尽量靠右。如果 $a_l \times a_{l+1} \times \cdots \times a_m$ 的末尾有 $k$ 个零，那么我们就将 $l$ 更新为 $m + 1$；否则我们将 $r$ 更新为 $m$。通过这样的方式，我们可以找到最右侧的满足条件的位置 $m$。