[C++知识库]C. 子序列（尺取法）

题目：https://www.malic.xyz/archives/3117/3
刚学了尺取法 没找到测评平台 也不知道写的是否正确
尺取法如下

代码``

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>

using namespace std;
const int maxn = 5e7+10;
const long long Mod = 1e9+7;
const int INF = 0x3f3f3f;
long long n,s,a1,b,T;
long long a[maxn];

int main()
{

    cin>>n>>s;
    cin>>a1>>b;
    a[1]=a1;
    for(int i=2; i<=n; i++)
    {
        a[i]=a[i-1]*b%Mod;
    }
    int i=1,j=1;
    long long sum=0;
    int ans=INF;
    while(1)//尺取核心 双指针
    {
        while(j<=n&&sum<s)
        {
            sum+=a[j++];
        }
        if(sum<s) break;
        ans=min(ans,j-i);
        sum-=a[i++];
    }
    if(ans==INF)
        cout<<"-1"<<endl;
    else
        cout<<ans<<endl;
    return 0;
}