1非负包括0啊,开始没考虑到,直接把整个数组当成一个区间来求了 ,还迟迟找不着Bug,我真是越来越憨了……先考虑一个区间不包括0的情况,比如N=7 V=9 Ai依次是2 2 2 8 1 1 2 起初pre=1;nex=1;mul=1;以pre为起点,让nex往后移动,并更新mul*=a[nex];直到mul>=V;说明nex及其之后的下标都可以,cnt+=4,此时nex<mark>4;mul</mark>64,之后让pre后移,并且更新mul/=a[pre];发现此时mul>=V;即此时以pre为起点,nex及其以后的下标中间的区间仍可以,更新cnt+=4;pre不断后移……直到pre<V,然后再将nex后移更新mul值。。。。题目Ai应为可能为0所以要划分区间,计算每一个不包含0 的区间求和即可,注意V==0要特殊考虑代码奉上
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define pi acos(-1.0)
#define e exp(1.0)
typedef long long ll;
const ll maxn=1e5+7;
ll T,N,V,cnt;
ll a[maxn];
void Han(ll beg,ll end)
{
ll pre,nex,mul=1;
pre=beg;
nex=beg;
while(nex<=end)
{
if(mul*a[nex]>=V)
{
mul*=a[nex];
cnt+=(end-nex+1);
mul/=a[pre];
pre++;
while(mul>=V&&pre<=nex)
{
cnt+=(end-nex+1);
mul/=a[pre];
pre++;
}
if(mul<V)
nex++;
else
nex=pre;
}
else
{
mul*=a[nex];
nex++;
}
}
return ;
}
int main()
{
ios::sync_with_stdio(false);
cin>>T;
while(T--)
{
cin>>N>>V;
ll i,j;
for(i=1;i<=N;i++)
cin>>a[i];
cnt=0;
if(!V)
{
cout<<N*(N+1)/2<<endl;
continue;
}
ll l,r;
for(i=1;i<=N;i++)
{
if(a[i]>0)
{
l=i;
r=l+1;
while(a[r]>0&&r<=N)
r++;
if(a[r]==0)
{
i=r;
r--;
Han(l,r);
}
else
{
r=N;
i=N;
Han(l,r);
}
}
}
cout<<cnt<<endl;
}
return 0;
}