起因是最近在学习 $\text{LogTrick}$ 的时候，遇到一道关于乘法的题，想了挺长时间，本来准备放弃这道题的，
但还是通过其他手段AC了这道题~

---

不多废话，正题开始 题目链接

一、题目大意

---

题目意思还是简单的，统计满足区间所有元素和等于区间所有元素乘积的个数，下文将区间和简称 S, 区间乘积简称 P

二、解题思路

首先如果我们暴力枚举区间子数组的话，时间复杂度为 $O(n^2)$ ，当数据范围 n 在 $1\le n\le 2\ast 10^5$时，是会超时的。通过观察在暴力过程中，发现子区间中乘法操作 P 增长速度是远大于其 S 的增长速度的，这容易让我们想到通过 $\text{LogTrick}$ 来优化原暴力算法，在暴力枚举子区间的基础上添加限制，当 P > 整个数组和时，我们及时终止内层循环。换句话说，利用了乘积指数级增长的特性，剪枝掉内层循环中多余的次数，使其时间复杂度控制在$O(n\cdot \log U)$，其中 U 为乘积上限。

---

1.特殊情况

特殊的，当数组中存在大量的 1 或全为 1 的时候，程序时间复杂度依然是 $O(n^2)$

2.进一步观察

我们可以将 P 和 S 分为 3 中情况 ：

• P = S 区间乘积等于区间和为合法情况
• P > S 考虑到若当前区间左右两侧有 1 的存在，我们可以将这些 1 视为改区间的一部分，由于不管加入多少 1 也不会影响 P 的变化，但可以增加 S 来使其成为一个合法子区间 P == S
• P < S 这时不管加入区间左右两侧多少个 1 也不会使其成为一个合法子区间

启发： 回到原先的问题中，当存在大量的 1 引发的超时问题，可以不考虑这些 1，将这些 1 从数组中移除掉，只考虑它们的乘积。

3、算法

ans 统计符合要求的区间数量，由于每个元素均符合要求所以ans 初始值为 n

• 在枚举去除 1 后数组的乘积时，我们需要原数组没有移除 1 的区间和 S ，我们可以使用前缀和维护
• 当 P > S 时，还需要区间左端点 L 左侧 1 的个数和右端点 R + 1中 1 的个数，即区间左右端点 1 的个数，我们用 L_one 数组表示 a[i] 左侧 1 的个数， 在加上可以使其成为合法子区间的数量
• P == S 时，为合法子区间，答案 + 1
• P < S时，不和法区间

补充： 给出具体 P > S 的例子，前提左右两侧1个数能够使S = P，满足S + 左右两侧1的个数 >= P

---

三、Code

#include <bits/stdc++.h>
using namespace std;

using u64 = unsigned long long;
using i64 = long long;
using u32 = unsigned;
using u128 = unsigned __int128;
using i128 = __int128;

void solve() {
    int n; cin >> n;
    vector<i64> a(n + 1), f(n + 1), L_one(n + 1); // a: 移除1后的数组  f:包括1的前缀和数组  L_one: 移除后a[i]左侧1的个数
    int ln = 0; // a数组大小
    for (int i = 0; i < n; ++i) {
        int x; cin >> x;
        if (x != 1) {
            a[ln] = x;
            f[ln + 1] = f[ln] + a[ln] + L_one[ln];
            ln += 1;
        } else {
            L_one[ln] += 1;
        }
    }
    i64 total = f[ln] + L_one[ln]; // 原数组总和 原数组右侧可能含有1, 加上右侧1的个数

    i64 ans = n; // 单个元素符合定义
    for (int i = 0; i < ln; ++i) {
        i64 p = a[i];
        for (int j = i - 1; j >= 0; --j) {
            p *= a[j];
            if (p > total) { // Log优化
                break;
            }
            i64 s = f[i + 1] - f[j] - L_one[j]; // 区间和

            if (s > p) {  // 不和法区间
                continue;
            }
            if (s == p) { // 合法区间
                ans += 1;
            } else { // 需要补充左右两侧的1
                i64 d = p - s; // 还需要补充1个数
                i64 left = min(d, L_one[j]); // 区间左侧1个数
                i64 right = min(d, L_one[i + 1]); // 区间右侧1个数
                if (left + right >= d)  ans += left + right - d + 1;
            }
        }
    }
    cout << ans << '\n';
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    while (t--) {
        solve();
    }
    return 0;
}

---

最后如果有其他问题，欢迎在评论区留言 ~