三元组计数 - 代码源竞赛平台

题目描述

给定一个长度为 $n$ 的整数序列 $a_1,a_2,\ldots,a_n$，每个元素的值都在 $1$ 到 $5$ 之间。

你需要从中选出三个下标 $i,j,k$，使它们同时满足：

• $1\le i<j<k\le n$；
• $a_i>a_k>a_j$；
• $a_i+a_k$ 能被 $a_j$ 整除 （即 $(a_i + a_k) \bmod a_j = 0$）。

请计算满足条件的下标三元组 $(i,j,k)$ 的数量。

输入格式

第一行包含一个整数 $n$，表示序列的长度。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示给定的序列。

输出格式

输出一个整数，表示满足条件的三元组数量。

样例

4
5 2 3 4

2

6
5 5 2 2 3 3

8

样例解释

对于样例 $1$，满足条件的下标三元组共有两个：

• $(1,2,3)$：对应的元素为 $(5,2,3)$，有 $5>3>2$，且 $5+3=8$ 能被 $2$ 整除。
• $(1,3,4)$：对应的元素为 $(5,3,4)$，有 $5>4>3$，且 $5+4=9$ 能被 $3$ 整除。

对于样例 $2$，$i$ 可以取 $1$ 或 $2$，$j$ 可以取 $3$ 或 $4$，$k$ 可以取 $5$ 或 $6$。这些选择对应的元素均为 $(5,2,3)$，满足所有条件，因此答案为 $2\times2\times2=8$。

数据规模

本题各子任务单独计分。须通过某子任务包含的所有测试点，方可获得该子任务的分数。

子任务编号	分数	$n\le$
$1$	$40$	$200$
$2$	$60$	$2\times 10^5$

对于 $100\%$ 的数据，$3\le n\le2\times 10^5$，$1\le a_i\le5$。