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 xa_l⋅a_{l1}⋅a_{l2}…a_rxal​⋅al1​⋅al2​…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的个数二分查找定位合法区间边界。关键操作预处理因子前缀和枚举左端点两次二分查找确定合法右端点范围并累加数量。效率保障前缀和线性预处理二分对数级查询整体复杂度低完美适配大数据量处理需求。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvt;typedefpairll,llpll;constll N1e710;constll p1e97;constll INF1e18;constll M5e310;intmain(){ll t;cint;while(t--){ll n,k;cinnk;vectorllv(n1);vectorllv1(n1,0);vectorllv2(n1,0);for(ll i1;in;i){cinv[i];while(v[i]%50){v[i]/5;v2[i];}while(v[i]%20){v[i]/2;v1[i];}v2[i]v2[i-1];v1[i]v1[i-1];}ll ans0;for(ll i1;in;i){ll li;ll rn;while(lr){ll midl(r-l)/2;ll cmin(v1[mid]-v1[i-1],v2[mid]-v2[i-1]);if(ck)rmid-1;elselmid1;}ll lrl;rn;while(lr){ll midl(r-l)/2;ll cmin(v1[mid]-v1[i-1],v2[mid]-v2[i-1]);if(ck)rmid-1;elselmid1;}ans(r-lr1);}coutansendl;}return0;}