转载请注明出处:http://tokitsukaze.live/

题目链接:http://codeforces.com/problemset/problem/992/D


题意:给一个序列和一个k,求有多少个区间,区间积/区间和=k。


题解:
满足题目条件的区间中,非1的数字的个数一定不会超过log个。所以先处理出对于每个数,右边第一个非1的数字的位置。枚举区间左端点,每次暴力跳log次,复杂度O(n64)。
有两个需要注意的地方:
1.当跳过一段1时,这一段1中可能会有满足条件的右端点,但如果只判断(区间积小于上一个右端点的区间和
k,且区间积大于等于(上一个右端点的区间和+跳过的1的个数)*k)的话,会wa13。原因是没有判断区间积是否是k的倍数。
2.要用除法判断是否爆ll。不然可能会wa15或者wa133。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define mem(a,b) memset((a),(b),sizeof(a))
#define MP make_pair
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
using namespace std;
#define _GLIBCXX_PERMIT_BACKWARD_HASH
#include <ext/hash_map>
using namespace __gnu_cxx;
struct str_hash{size_t operator()(const string& str)const{return __stl_hash_string(str.c_str());}};
typedef long long ll;
typedef unsigned long long ull;
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PDD pair<double,double>
#define VI vector<int>
#define VL vector<ll>
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-6;
const int MAX=2e5+10;
const ll mod=998244353;
ll a[MAX],bit[MAX],r[MAX];
int main()
{
ll n,k,i,j,nex,now,ans,pre;
while(~scanf("%lld%lld",&n,&k))
{
bit[0]=0;
for(i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
bit[i]=bit[i-1]+a[i];
r[i]=i+1;
}
bit[n+1]=bit[n];
nex=n+1;
for(i=n;i>=1;i--)
{
while(i>=1&&a[i]==1) r[i--]=nex;
r[i]=nex;
nex=i;
}
r[n]=n+1;
ans=0;
for(i=1;i<=n;i++)
{
// cout<<r[i]<<endl;
now=1;
pre=i;
for(j=i;j<=n+1;j=r[j])
{
if(pre!=j&&now%k==0&&(bit[pre]-bit[i-1])*k<now&&(bit[j-1]-bit[i-1])*k>=now) ans++;
if(j==n+1) break;
if(now>=4e18/a[j]) break;
now*=a[j];
if(now==(bit[j]-bit[i-1])*k) ans++;
pre=j;
if(j==n) break;
// cout<<i<<" "<<j<<" "<<ans<<endl;
}
}
printf("%lld\n",ans);
}
return 0;
}