409568: GYM103633 B Floor or xor ?

You are given an array $$$A$$$ of $$$N$$$ numbers and an integer $$$T$$$. Find the number of tuples of indices $$$(i,j,k,l)$$$ such that $$$\lfloor \frac{A_i}{A_j} \rfloor + \lfloor \frac{A_k}{A_l} \rfloor$$$ = $$$T$$$.

Two tuples are $$$A$$$ and $$$B$$$ are distinct if there exists some $$$i$$$ such that $$$A_i \neq B_i$$$. For example , (1,1,2,4) is not the same as (1,2,1,4). Note that there may be repetitions.

Print the answer modulo $$$MOD$$$.

The input consists of $$$N$$$,$$$T$$$ and $$$MOD$$$ followed by an array $$$A$$$ of size $$$N$$$.

Print one integer : The number of tuples modulo $$$MOD$$$.

• $$$N \le 10^5$$$ , $$$1 \le A_i \le 5 \cdot 10^5$$$, $$$T \le 5 \cdot 10^5$$$, $$$MOD \le 10^9$$$.
• For test data worth $$$20$$$ points , $$$N \le 50$$$ , $$$1 \le A_i \le 10^5$$$.
• For another $$$20$$$ points, $$$N \le 2000$$$, $$$1 \le A_i \le 10^5$$$.
• For another $$$30$$$ points, $$$1 \le A_i \le 10^5$$$
• For the remaining $$$30$$$ points , there are no further restrictions.

3 2 666013
1 1 1

81

10 2 9821672
372960 389034 286291 199826 189342 219065 129531 340535 69643 177416

2410

In the first sample it is easy to see that every possible tuple is good since $$$\lfloor \frac{1}{1} \rfloor + \lfloor \frac{1}{1} \rfloor = 2$$$. Thus print $$$3^4$$$ mod $$$666013 = 81$$$.

The second sample has a beautiful explination , but unfortunately it is too long to write.