思路：双指针

末尾0的数量可以等价于数字中2的乘积数量和5的乘积数量的最小值，比如$60=2^2\times 3\times 5^1$，因此60的末尾0为$min(1,2)=1$

很显然，区间长度越大，末尾0的个数越多，因此符合单调性，可以考虑使用双指针算法求解

我们首先统计整个数组的2的乘积数量和5的乘积数量，然后定义两个指针维护区间$[l,r]$

若$[l,r]$区间中有$min(cnt2,cnt5)\ge k$，则答案累加$n-r$即可，$l$指针右移

Python

n, k = list(map(int, input().split()))
a2 = [0] * n
a5 = [0] * n
a = list(map(int, input().split()))
for i in range(n):
    while a[i] % 2 == 0:
        a[i] //= 2
        a2[i] += 1
    while a[i] % 5 == 0:
        a[i] //= 5
        a5[i] += 1
cnt2 = sum(a2)
cnt5 = sum(a5)
left = 0
ans = 0
for right in range(n):
    cnt2 -= a2[right]
    cnt5 -= a5[right]
    while left <= right and min(cnt2, cnt5) < k:
        cnt2 += a2[left]
        cnt5 += a5[left]
        left += 1
    ans += right - left + 1
print(ans)

题目描述

小美拿到了一个大小为$n$的数组，她希望删除一个区间后，使得剩余所有元素的乘积未尾至少有$k$个0。小美想知道，一共有多少种不同的删除方案?

输入描述

第一行输入两个正整数$n,k$

第二行输入$n$个正整数$a_i$，代表小美拿到的数组

$1\le n,k\le 10^5$

$1\le a_i\le 10^9$

输出描述

一个整数，代表删除的方案数

样例

输入

5 2
2 5 3 4 20

输出

4

说明

第一个方案，删除[3]

第二个方案，删除[4]

第三个方案，删除[3,4]

第四个方案，删除[2]