题解 | #Kevin喜欢零(困难版本)#

一看到“末尾有几个 ”，就能想到只和因子 有关,子段答案就是

然后套路是把“恰好 ”改成“至少 减至少 ”，前缀和配双指针线性统计就行。

void solve(){
    int n;ll k;cin>>n>>k;
    vi a(n+1);
    for(int i=1;i<=n;++i)cin>>a[i];
    vll p2(n+1),p5(n+1);
    for(int i=1;i<=n;++i){
        int x=a[i],c2=0,c5=0;
        while(x%2==0){
            x/=2;
            ++c2;
        }
        while(x%5==0){
            x/=5;
            ++c5;
        }
        p2[i]=p2[i-1]+c2;
        p5[i]=p5[i-1]+c5;
    }
    auto work=[&](ll kk)->ll{
        ll res=0;
        int i2=-1,i5=-1;
        for(int i=1;i<=n;++i){
            while(i2+1<=n&&p2[i2+1]<=p2[i]-kk)++i2;
            while(i5+1<=n&&p5[i5+1]<=p5[i]-kk)++i5;
            int t=min(i-1,min(i2,i5));
            if(t>=0)res+=t+1;
        }
        return res;
    };
    ll ans=work(k)-work(k+1);
    cout<<ans<<endl;
}