子序列肯定不可能是无限长的
由于amax=1e8 nmax=2e5 kmax=1e5
则summax=1e82e51e5=2e18 而longlong刚好能hold住
那也就是说一个子序列里面非1的个数不超过64个（longlong范围是2^64）
那我们可以把连续的1缩成一坨 然后枚举每个点 暴力地往后找
具体的实现：记le[i]记录每个数左边第一个不是1的数在哪儿 然后用类似链表的方法遍历 如果乘积马上就要爆longlong了 就马上break
这样复杂度O(64*n)
#include<bits/stdc++.h> #define N 200005 #define ll long long using namespace std; template<class T> inline void read(T &x) { x=0; static char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); } int n,le[N],ans; ll k,a[N]; inline bool Overflow(ll mul,ll x) { if(mul>LLONG_MAX/x) return true; return false; } int main() { read(n); read(k); for(int i=1;i<=n;i++) read(a[i]); for(int i=1;i<=n;i++) { if(a[i-1]!=1) le[i]=i-1; else le[i]=le[i-1]; //记录每个数左边第一个不是1的数在哪儿 } for(int i=1;i<=n;i++) { ll sum=a[i],mul=a[i]; if(mul==sum*k) ans++; for(int pre=i,now=le[i];;pre=now,now=le[now]) { ll del=mul-sum*k; if(del>0&&del%k==0&&del/k<pre-now) ans++; //判断跳过的这段1 能否更新答案 if(!now||Overflow(mul,a[now])) break; mul*=a[now]; sum+=a[now]+(pre-now-1); if(mul==sum*k) ans++; } } cout<<ans<<endl;; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9846540.html
相关资源：各显卡算力对照表！