题解 | #最小的数字#

D简单版本的做法（二分）：因为0的个数只会越乘越多，故可用前缀积维护，满足二分性，每次枚举左端点，二分右端点，即可计算出答案。

using namespace std;
using ll = long long;

const int N = 2e5 + 5;
ll a[N];
ll T[N];
int n, k;

ll check(ll q) { // 计算后导零
	ll res = 0;
	while (q && q % 10 == 0) {
        res += 1;
		q /= 10;
	}
	return res;
}

void solve() {
	cin >> n >> k;
	T[0] = 1;
    ll ans = 0;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		T[i] = T[i - 1] * a[i];
	}
	for (int l = 1; l <= n; l++) { // 枚举左端点
		int tl = l, tr = n;

		while (tl < tr) {  // 找到最小的右端点
			int mid = tl + tr >> 1;
			if (check(T[mid] / T[l - 1]) >= k)
				tr = mid;
			else
				tl = mid + 1;
		}
		int ans1 = tl;
		
		tl = l, tr = n;
		while (tl < tr) {  // 找到最大的右端点
			int mid = tl + tr + 1 >> 1;
			if (check(T[mid] / T[l - 1]) <= k)
				tl = mid;
			else
				tr = mid - 1;
		}
		
		if (check(T[ans1] / T[l - 1]) == k)  // 判断是否找到区间
			ans += tl - ans1 + 1;		
	}
	cout << ans << endl;
}

int  main(void) {
	int m;
	cin >> m;
	while (m--)
		solve();
	return 0;
}