思维，dp，枚举

题意：

分析:

这题我拿到手时，是一脸懵逼。我不知道该从哪里下手才好。
我率先的想法是，统计每一个索引i处，开个数组记录他后面与他数值相等的索引。

再从头到尾遍历，遍历到i时，一一遍历他的索引数组。
假设遍历到了j 我们确定了第三个数索引为j 第一个为i
然后在i到j之间再遍历去确定第二个数字的索引，
然后同样进去其中的数组，寻找第四个数字的索引，必须保证索引大于第三个。这里可以利用二分。

但是，着其实是很麻烦的。时间复杂度直接爆表！！！！！！

那么我们看看上面的哪里超时的了。
我们先确定了第一个数字，然后再确定第三个数字，然后再确定第二个数字，最后确定第四个数字。

虽然我们进行了一些优化，没有暴力的四成循环。但是这种确认顺序本身就已经很低效了。
因为确定了，第一个和第三个后我们对第二个和第四个的约束作用仅仅只有区间的约束。

如果我们改变确认的顺序呢？
我们直接确认第二个和第三个呢？
如果我们知道第二个和第三个，那么我们便知道了第一个数字的值和第一个数字的所在区间
同样我们也知道了第二个数字的值和第二个数字的所在区间。

考虑到数据范围我们可以直接遍历第二个数字和第三个数字。
假如第二个数字索引i，第三个j。
那么我们只需知道i之前为a[j]的有多少个，j之后为a[i]的有所少个。
二者相乘，我们便求出了，当第二个数字与第三个数字确定时贡献的组合数。

而前i个种有几个为a[i]我们可以直接用dp方法求出。
dp[i][j]表前i个值为j的有几个
dp[i][j] = dp[i-1][j] + [a[i] == j]

同样，对于后面的也可以开一个dp，但是也不需要。我们可以直接dp[n][a[i]] - dp[j][a[i]]

很简单，很巧妙。这是考验你有没有这种思维！！
能不能想到先确定第二个和第三个数，这两个数确定了之后对整体的约束最大！！！！！！！！

代码如下：

#include<iostream>
using namespace std;
typedef long long ll;
const int max_n = 3100;
int n;
int dp[max_n][max_n];           //dp[i][j]  表示前i个有多少j
int a[max_n];

int main() {
    ios::sync_with_stdio(0);
    int T;cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1;i <= n;i++)cin >> a[i];
        for (int i = 1;i <= n;i++)
            for (int j = 1;j <= n;j++)
                dp[i][j] = 0;

        //求解dp数组
        for (int i = 1;i <= n;i++)
            for (int j = 1;j <= n;j++)
                dp[i][j] = dp[i - 1][j] + (j == a[i]);

        ll ans = 0;

        //枚举中间两个数字(这两个数字直接决定了两边的数字取什么)
        for (int i = 1;i <= n;i++)
            for (int j = i + 1;j <= n;j++)
                ans += (ll)dp[i - 1][a[j]] * (ll)(dp[n][a[i]] - dp[j][a[i]]);
        cout << ans << endl;
    }
}

真的很巧妙，主要还是思维。这里面，dp被当成了一种工具