Riolku's Mock CCC S2 - Keen Keener Sequence (Hard Version)

View as PDF

Submit solution

All submissions

Best submissions

Points: 12

Time limit: 2.0s

Memory limit: 512M

Authors:

Plasmatic, Riolku

Problem types

Note: this is a harder version of this problem. The only difference between this problem and that one are the constraints.

Keen Keen Guglor the Keener is keen to know more about a sequence of $N$ ~N~ numbers he received yesterday, labeled $a_1, a_2, \dots, a_N$ ~a_1, a_2, \dots, a_N~. More specifically, he wants to compute the number of ordered $4$ ~4~-tuples $(i,j,k,l)$ ~(i,j,k,l)~ such that $i,j,k,l$ ~i,j,k,l~ are pairwise distinct and $a_i \times a_j = a_k \times a_l$ ~a_i \times a_j = a_k \times a_l~. Unfortunately, even though he is so keen to know the answer to his question, he was unable to figure it out himself and hopes that you could help him with the problem.

Constraints

$1 \le N \le 7 \times 10^3$ ~1 \le N \le 7 \times 10^3~

$1 \le a_i \le 10^9$ ~1 \le a_i \le 10^9~

Input Specification

The first line will contain the integer $N$ ~N~.

The second line will contain the space-separated integers $a_1, a_2, \dots, a_N$ ~a_1, a_2, \dots, a_N~.

Output Specification

On one line, output the number of $4$ ~4~-tuples as specified in the problem statement.

Sample Input 1

4
1 2 4 8

Sample Output 1

Explanation for Sample Output 1

Our $8$ ~8~ tuples are $(1, 4, 2, 3), (4, 1, 2, 3), (1, 4, 3, 2), (4, 1, 3, 2), (2, 3, 1, 4), (3, 2, 1, 4), (2, 3, 4, 1)$ and $(3, 2, 4, 1)$ ~(3, 2, 4, 1)~.

Sample Input 2

4
5 5 5 5

Sample Output 2

Sample Input 3

10
1 4 8 6 2 9 4 2 5 3

Sample Output 3

Comments

0

luismo commented on Feb. 16, 2021, 10:16 p.m.

No editorial?

1

SuperClash commented on Feb. 16, 2021, 10:41 p.m. ← edited →

The editorial can be found on the page of the original problem: https://dmoj.ca/problem/rccc1s2