Kevin喜欢零(困难版本)【牛客tracker 每日一题】

Kevin喜欢零(困难版本)

时间限制：1秒 空间限制：256M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

本题分为简单版本和困难版本，二者唯一的区别是：简单版本有序列a aa所有元素乘积≤ 10 18 ≤10^{18}≤1018的限制，困难版本没有。

氧气少年最近喜欢上了零。

给出一个长度为n ( 1 ≤ n ≤ 2 ⋅ 10 5 ) n(1≤n≤2⋅10^5)n(1≤n≤2⋅105)的序列a ( 1 ≤ a i ≤ 10 9 ) a (1≤a_i≤10^9)a(1≤ai​≤109)，求这个序列中满足如下条件的连续子段[ a l … a r ] [a_l…a_r][al​…ar​]的数量：

• 令x = a l ⋅ a l + 1 ⋅ a l + 2 … a r x=a_l⋅a_{l+1}⋅a_{l+2}…a_rx=al​⋅al+1​⋅al+2​…ar​，那么x xx的末尾恰好有k ( 0 ≤ k ≤ 10 9 ) k(0≤k≤10^9)k(0≤k≤109)个零。

输入描述：

第一行包含一个整数T ( 1 ≤ T ≤ 10 5 ) T(1≤T≤10^5)T(1≤T≤105)，表示测试用例的组数。

对于每组测试用例：

第一行包含两个整数n ( 1 ≤ n ≤ 2 ⋅ 10 5 ) n(1≤n≤2⋅10^5)n(1≤n≤2⋅105)和k ( 0 ≤ k ≤ 10 9 ) k(0≤k≤10^9)k(0≤k≤109)，表示序列的长度和题目中提到的后导零的数量；

第二行包含n nn个整数a 1 … a n ( 1 ≤ a i ≤ 10 9 ) a_1…a_n (1≤a_i≤10^9)a1​…an​(1≤ai​≤109)，表示该序列。

保证对于所有的测试用例，n nn的总和不超过2 ⋅ 10 5 2⋅10^52⋅105。

输出描述：

对于每组测试用例：

仅输出一行，包含一个整数，表示答案。

示例1

输入：

2 5 3 125 1 8 1 1 1 0 6

输出：

3 1

解题思路

本题核心是前缀和+二分查找求解子区间乘积末尾0 00个数恰好为k kk的数量：末尾0的数量由区间内因子2 22和5 55的总个数的最小值决定。先遍历数组，分解每个数字的2 、 5 2、52、5质因子数量，计算前缀和数组，实现O ( 1 ) O(1)O(1)查询任意区间的因子总数。枚举每个左端点i ii，通过两次二分查找，定位满足条件的最小/最大右端点，快速统计以i ii为左端点的合法子区间数。累加所有左端点的结果得到最终答案，整体时间复杂度为O ( n log ⁡ n ) O(n \log n)O(nlogn)，高效适配大数据规模，精准统计合法子区间数量。

总结

核心逻辑：用2 、 5 2、52、5因子的前缀和快速计算区间末尾0 00的个数，二分查找定位合法区间边界。
关键操作：预处理因子前缀和，枚举左端点，两次二分查找确定合法右端点范围并累加数量。
效率保障：前缀和线性预处理，二分对数级查询，整体复杂度低，完美适配大数据量处理需求。

代码内容

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vt;typedefpair<ll,ll>pll;constll N=1e7+10;constll p=1e9+7;constll INF=1e18;constll M=5e3+10;intmain(){ll t;cin>>t;while(t--){ll n,k;cin>>n>>k;vector<ll>v(n+1);vector<ll>v1(n+1,0);vector<ll>v2(n+1,0);for(ll i=1;i<=n;i++){cin>>v[i];while(v[i]%5==0){v[i]/=5;v2[i]++;}while(v[i]%2==0){v[i]/=2;v1[i]++;}v2[i]+=v2[i-1];v1[i]+=v1[i-1];}ll ans=0;for(ll i=1;i<=n;i++){ll l=i;ll r=n;while(l<=r){ll mid=l+(r-l)/2;ll c=min(v1[mid]-v1[i-1],v2[mid]-v2[i-1]);if(c>=k)r=mid-1;elsel=mid+1;}ll lr=l;r=n;while(l<=r){ll mid=l+(r-l)/2;ll c=min(v1[mid]-v1[i-1],v2[mid]-v2[i-1]);if(c>k)r=mid-1;elsel=mid+1;}ans+=(r-lr+1);}cout<<ans<<endl;}return0;}