Written by @Yue_chen

题意：

给定一个长度为 n 的数组，和一个 p。

找长度为3。公比为p的子序列的个数。

思路：

直接枚举肯定超时。

枚举第一个数或最后一个数不能保证另外两个数的顺序，因此枚举中间的数，保证统计的子序列不重复，并且有序。

所以我们需要时刻保存前缀和后缀。

枚举时，在后缀中查找a[i] * p的数量，在前缀中查找 a[i]/p的数量，如果a[i]%p != 0 直接跳过。

合法时直接 ans += 前缀合法数量 * 1 * 后缀合法数量。

时间复杂度O(nlog2n)

AC代码：

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

using i64 = long long;

void solve() {
    int n, p; cin>>n>>p;
    
    map<i64, i64> mp1, mp2;//mp1为前缀，mp2为后缀
    vector<int> a(n+1);
    for(int i=1; i<=n; ++i) {
        cin>>a[i];
        mp2[a[i]]++;
    }
    
    i64 ans = 0;
    for(int i=1; i<=n; ++i) {//枚举中间的数
        mp2[a[i]]--;
        if(a[i]%p == 0) {
            i64 pre = 1ll * a[i] / p;
            i64 suf = 1ll * a[i] * p;
            if(mp1.count(pre) and mp2.count(suf)) {
                ans += mp1[pre] * mp2[suf];
            }
        }
        mp1[a[i]]++;
    }
    
    cout<<ans<<"\n";
}

signed main(void) {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int t=1; //cin>>t;
    while (t--) solve();
    return 0;
}