题意，在原数组中找到3个下标,a<b<c，使得A[a]*k=A[b],A[b]*k=A[c]
问(a,b,c)这样的三元组有多少个
思路：
dp[i][0]表示以i为A[a]的个数
dp[i][1]表示以i为A[b]的个数
dp[i][2]表示以i为A[c]的个数
可以得到转移方程
如果i%k==0 dp[i][2]+=dp[i/k][1]
如果i%k==0 dp[i][1]+=dp[i/k][0]
dp[i][0]++
其实这是滚动数组，，然后顺着扫一遍就做完了
但是，考虑到i最大可以到1e9,所以要用hash将节点的值缩小，也可以用map搞，道理都是一样的
有个要注意的地方，，必须是先更新2，在更新1，再更新0，顺序不能反过来
因为k=1的特殊情况时，如果先更新0，再更新1，再更新2，就会被重复算
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
#include<map>
#include<string>
#include<iostream>
#include<functional>
#include<algorithm>using namespace std;
typedef long long LL;
typedef pair<int, int> PII;const int MX = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int HS = 1000007;LL H_T[MX];
int H_head[HS], H_next[MX], H_rear;int Hash(LL S) {return S % HS;
}void Hash_init() {H_rear = 0;memset(H_head, -1, sizeof(H_head));memset(H_next, -1, sizeof(H_next));
}int Hash_query(LL S) {int h = Hash(S);for(int i = H_head[h]; ~i; i = H_next[i]) {if(H_T[i] == S) return i;}H_T[H_rear] = S;H_next[H_rear] = H_head[h];H_head[h] = H_rear;return H_rear++;
}LL dp[MX][3];int main() {//freopen("input.txt", "r", stdin);int n; LL k, t;Hash_init();scanf("%d%I64d", &n, &k);for(int i = 1; i <= n; i++) {scanf("%I64d", &t);int id = Hash_query(t);if(t % k == 0) {dp[id][2] += dp[Hash_query(t / k)][1];}if(t % k == 0) {dp[id][1] += dp[Hash_query(t / k)][0];}dp[id][0]++;}LL ans = 0;for(int i = 0; i < H_rear; i++) {ans += dp[i][2];}printf("%I64d\n", ans);return 0;
}