好题集第四篇。
题意
给一个长度为 $n$ 的正整数序列 $a$ 和一个常数 $k$，求 $a$ 中有多少对 $(l,r)$ 满足 $\frac{\prod_{i=l}^{r}}{\sum_{i=l}^{r}}=k$。这里用 \(mina\) 表示数组中的最小值，用 \(maxa\) 表示数组中的最大值。
对于前 \(30\%\) 的测试点，\(n\le10\)，\(maxa\le10\)。
对于前 \(60\%\) 的测试点，\(n\le100\)。
对于前 \(80\%\) 的测试点，\(mina\ge2\)。
对于 \(100\%\) 的测试点，\(n\le 2\times10^5\)，\(k\le10^5\)，\(maxa\le10^8\)，\(mina\ge1\)。
Hint 1
想想对于 $60$ 分的数据的做法。Hint 2
考虑 $80$ 分的数据，能不能发现“人类智慧”？Hint 3
考虑 $100$ 分的数据，对于有 $1$ 出现的情况，如何处理这些 $1$?Solution
设一段区间的乘积为 $tim$，区间和为 $sum$。我们来看一堆 \(1\) 连续的情况。
假如现在区间 \([l,r]\) 全部都是 \(1\)，那么 \(tim=1\)，\(sum=r-l+1\)。假设现在我们后面又多了 \(cnt\) 个 \(1\)，那么现在如果它要计入贡献的话就要满足 \(tim=k\times(sum+cnt)\)，也就是 \(1=k\times(sum+cnt)\)。于是我们得到 \(cnt\) 的范围: \(1\le cnt\le\frac{1}{k}-sum\)。所以在这个范围内的 \(cnt\) 就可以计数。
但是直接枚举每一个 \(1\)，复杂度就会变成 \(O(n^2)\)，如何优化呢？
我们可以维护一个 \(rt\) 数组，来记录这一段连续的 \(1\) 的右端点。所以我们遇到这些 \(1\) 就可以一起处理，而不是直接遍历，从而把复杂度降下来。
总时间复杂度均摊 \(O(n)\)。
Code
#include <bits/stdc++.h>
#define loop(i,a,b) for(int i=(a);~i;i=(b))
#define eb emplace_back
#define pb push_back
#define print(x,c) write(x),putchar(c),flush()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
constexpr int N = 2e5 + 15;
constexpr ll INF = 2e18;namespace FAST_IO {
#define IOSIZE 300000char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)template <typename T> inline void read (T &x) { x = 0; T f = 1;char ch = getchar ();while (!isdigit (ch)) {if (ch == '-') f = -1; ch = getchar ();}while (isdigit (ch)) {x = (x << 1) + (x << 3) + (ch ^ '0'); ch = getchar ();} x *= f;}template <> inline void read (double &x) { x = 0; int f = 1;char ch = getchar ();while (!isdigit (ch)) { if (ch == '-') f = -1; ch = getchar ();} while (isdigit (ch)) x = x * 10 + (ch - '0'), ch = getchar ();if (ch == '.') {ch = getchar (); for (double t = 0.1; isdigit (ch); t *= 0.1) x += t * (ch - '0'), ch = getchar ();}x *= f;}inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }template <typename T, typename ...Args> inline void read (T &x, Args &...args) {read(x); read(args...);}template <typename T> inline void write (T x) { if (x < 0) putchar ('-'), x = -x; if (x > 9) write (x / 10); putchar (x % 10 + 48);}inline void write(char *x) { while (*x) putchar(*x++); }inline void write(const char *x) { while (*x) putchar(*x++); }inline void flush() { if (p3 != obuf) { fwrite(obuf, 1, p3 - obuf, stdout);p3 = obuf;}}
}
using namespace FAST_IO;int n;
ll k;
int a[N];
ll ans;
int rt[N];int main () {read (n, k);for (int i = 1; i <= n; ++ i) {read (a[i]);}for (int i = n; i >= 1; -- i) {if (a[i] == 1) {rt[i] = (a[i + 1] == 1) ? rt[i + 1] : i;} else rt[i] = i;}for (int l = 1; l <= n; ++ l) {ll sum = 0, tim = 1;for (int r = l; r <= n; ) {if (a[r] == 1) {int cnt = rt[r] - r + 1;if (tim % k == 0) {ll tmp = tim / k - sum;if (tmp >= 1 && tmp <= cnt) ++ ans;}sum += cnt;r = rt[r] + 1;} else {if (tim * a[r] > INF) break;tim *= a[r];sum += a[r];if (tim == k * sum) ++ ans;++ r;}}}print (ans, '\n');return 0;
}