- it
- 牛客乘法师
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 == 4; mul == 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;
}
