#	User	Rating
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

PROBLEM: (Source)

Given $$$n$$$ $$$d$$$-dimensional vectors $$$v_1, v_2, \cdots, v_n$$$, output $$$i > j$$$ such that $$$v_i \cdot v_j \equiv 0 \mod k$$$, or determine that such indexes do not exist.

Constraints: $$$n \leq 10^5, d \leq 20, 2 \leq k \leq 3$$$

$$$k = 2$$$

The main idea is check for every $$$i$$$ if there exists a $$$j$$$ satisfying the requirement. Keep in mind that here, $$$i$$$ can be treated as a constant. Therefore, requirement is equivalent to negating

$$$\forall 1\leq j\leq i-1, v_i \cdot v_j \not\equiv 0\mod 2\\\\$$$ $$$\forall 1\leq j\leq i-1, \sum_{k=1}^d v_{ik}v_{jk} \equiv 1\mod 2\\\\$$$ $$$\sum_{j=1}^{i-1}\sum_{k=1}^d v_{ik}v_{jk} \equiv i - 1\mod 2\\\\$$$ $$$\sum_{k=1}^d v_{ik}\sum_{j=1}^{i-1}v_{jk} \equiv i - 1\mod 2\\\\$$$

The inner summation can be computed quickly using prefix sum. Therefore complexity is O($$$nd$$$) where the $$$n$$$ comes from looping through every $$$i$$$.

$$$k = 3$$$

Now we deal with $$$k = 3$$$. Same idea, but now we don't have the nice property of $$$\not\equiv 0 \implies \equiv 1$$$. However, we can do something clever:

$$$\forall 1\leq j\leq i-1, v_i \cdot v_j \not\equiv 0\mod 3\\\\$$$ $$$\forall 1\leq j\leq i-1, (\sum_{k=1}^d v_{ik}v_{jk})^2 \equiv 1\mod 3\\\\$$$ $$$\sum_{j=1}^{i-1}\Big(\sum_{k=1}^d v_{ik}v_{jk}\Big)^2 \equiv i - 1\mod 3\\\\$$$ $$$\sum_{j=1}^{i-1}\sum_{k=1}^d \sum_{l=1}^d v_{ik}v_{jk}v_{il}v_{jl} \equiv i - 1\mod 3\\\\$$$ $$$\sum_{k=1}^d \sum_{l=1}^d v_{ik}v_{il} \Big(\sum_{j=1}^{i-1}v_{jk}v_{jl}\Big) \equiv i - 1\mod 3\\\\$$$

The inner summation can again be stored from previous queries. Therefore the time complexity is $$$O(nd^2)$$$.

Details:

1) The logic above implies that if $$$\sum \not\equiv i-1 \mod 3$$$, there will be a pair of vectors with inner product divisible by $$$3$$$. HOWEVER, it is possible that such pair exists but still bypasses all tests. For example taking $$$d = 1, k = 2, v_1 = 0, v_i = 1 \forall 2\leq i\leq n$$$, the vectors will satisfy that test above. Therefore, it is necessary to shuffle the vectors before applying the check.

2) In the original problem, we also have to restore the index. If we know a given $$$i$$$ fails, we can simply check all $$$j<i$$$ in $$$O(nd)$$$ time.

My implementation can be found here