Educational Codeforces Round 94 D-Zigzags
Ryo_Yamada
·
·
个人记录
刚看到题的时候，这 D 是二维偏序？不做了不做了。第二眼：n \leq 2000，wc？这题好水啊，水掉水掉。
看完题之后，*，又是计数题，自闭。
求 a_i = a_k \operatorname{and} a_j = a_l 且 1 \leq i < j < k < l \leq n 的个数。
用 $k_{i,j}$ 表示 $k \leq j$ 且 $a_i=a_k$ 的个数，$g_{i,j}$ 表示 $k \geq j$ 且 $a_i=a_k$ 的个数。
之后~~一通乱搞~~直接计数就可以了，代码也不难理解。
$\text{Code}$：
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 3005;
int a[N];
int k[N][N], g[N][N];
int main() {
int T;
cin >> T;
while(T--) {
int n;
long long sum = 0;
cin >> n;
memset(k, 0, sizeof k);
memset(g, 0, sizeof g);
for(int i = 1; i <= n; i++) scanf("%d", a + i);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) k[i][j] = k[i][j - 1] + (a[i] == a[j]);
for(int j = n; j; j--) g[i][j] = g[i][j + 1] + (a[i] == a[j]);//预处理
}
for(int i = 3; i < n; i++) {
for(int j = 2; j < i; j++) {
sum += k[i][j - 1] * g[j][i + 1];
}
}
cout << sum << endl;
}
return 0;
}
```