rkm0959

중요한 사실은 어쨌든 $T = xor(A) \oplus xor(B)$가 고정값이라는 것이다. 

만약 특정 비트가 $T$에서 꺼져있다면, 뭘 하더라도 $xor(A), xor(B)$는 그 비트에서 같은 값을 갖는다.

다른 말로 하면, 그 비트는 우리가 굳이 신경쓰지 않아도 된다는 것이다. 알아서 강제되기 때문이다.

이제 $T$의 가장 큰 비트를 $xor(A)$에게 준다고 하자. 이 시점에서 $xor(A) > xor(B)$는 강제된다.

이제부터 우리의 목표는 $T$에서 켜진 비트를 최대한 $B$에게 주는 것이다. 이를 확인하려면 뭐가 필요할까?

"특정 상위 비트에 대해서 이 비트마스크를 가질 수 있는가"를 판별하는 방법이 필요하다.

주어진 수들을 체 $\mathbb{F}_2$ 위의 벡터로 보고 기저를 만들자. 이제 가우스 소거로 이걸 할 수 있다. 

결국 XOR prefix를 두 개로 쪼개서, 그 합을 최대화하는 것을 목표로 한다. 문제를 다르게 표현해보자.

어쨌든 쪼갠 두 값의 XOR 값을 고정이다. 또한, 첫 부분은 결국 이전에 등장한 XOR prefix가 된다.

즉, 값 $A$와 집합 $S$가 주어졌을 때, $x \in S$에 대하여 $x + (A \oplus x)$의 값을 최대화한다고 생각하자.

그런데 $x + y = x \oplus y + 2 (x \land y)$가 성립한다. 그러니 $x \land (A \oplus x)$를 최대화한다.

이건 결국, "$A$가 가지지 않는 비트 중 $x$가 갖는 비트"의 값을 최대화하는 문제가 된다.

마찬가지로 큰 비트부터 보면서, "이 mask를 포함하는 원소가 $S$에 존재하는가"를 물어보면 된다.

그런데 $S$는 쿼리를 대답하면서 커지는 집합이므로, 원소를 추가하면서 BFS를 조지면 이 쿼리를 쉽게 답할 수 있다. 

모든 간선을 $0$으로 만드는 것은, 모든 정점의 "인접한 간선들의 가중치의 XOR"을 $0$으로 만드는 것과 동치다.

증명을 하려면, 단순히 리프부터 시작해서 올라가면 된다. 애초에 사이클이 없으니 자명하다.

이제 이 값을 정점의 값으로 부르도록 하자. 이제부터 간선에 대한 생각을 버린다.

또한, 특정 경로에 속한 간선들에 $x$를 XOR하는 것은, 경로의 양쪽 끝점의 값에 $x$를 XOR하는 것과 같다.

이제 훨씬 문제가 편해졌다. 이때 큰 가정을 하나 하자. 정점의 값이 같은 것이 2개가 있는 경우, 한 번의 시행으로 두 값을 $0$으로 만들 수 있다. 

이 시행을 무조건 하는 것이 이득이라고 가정해보자. 이제 문제를 풀 수 있다.

이 가정의 장점은, 현재 상태를 비트마스크로 쓸 수 있다는 것이다. "현재 홀수 개 존재하는 값의 집합"으로 보면 된다.

시작하자마자 같은 값을 갖는 정점 2개를 쌍으로 묶어 전부 0으로 만들고, 각 값이 최대 한 번 존재하도록 한다.

이제 "두 정점을 잡아 $x$를 XOR한 후, 두 개 이상 존재하는 값을 묶어 처리"하는 것을 상태 이전으로 볼 수 있다.

이러한 상태 이전은 그래프의 정점 (비트마스크) 사이의 간선으로 볼 수 있고, 이제 최단 거리 문제가 된다. 끝.

$$E(f(s_1, s_2, \cdots, s_n)) = E( \sum_{k=1}^\infty [\exists_{1 \le i < j \le n} LCP(s_i, s_j) \ge k ])$$

$$= \sum_{k=1}^\infty P(\exists_{1 \le i < j \le n} LCP(s_i, s_j) \ge k) = \sum_{k=1}^\infty \left( 1 - P(\forall_{1 \le i < j \le n} s_i[0,k) \neq s_j[0, k)) \right)$$

$$= \sum_{k=1}^\infty \left( 1 - \frac{2^k(2^k-1) \cdots (2^k-n+1)}{(2^k)^n} \right)$$

가 되며 이는 전개 후 등비수열의 합으로 풀 수 있다. FFT를 쓰면 subquadratic 풀이도 가능. (분할정복/스털링 등)

근본적으로 EGF를 생각하기 편한 구조가 되겠다. 우리가 원하는 EGF는 결국 $$\prod_{i=1}^{k-1} \left( \sum_{j=0}^n \frac{g_{i, j}}{j!} x^j \right)$$ 가 된다. 여기서 $g$ 값들이 하나씩 바뀌는 것이 문제다. 모듈로가 NTT 모듈로고, 작으므로, 이 문제의 요령을 생각하자.

이제부터 적용할 모든 NTT는 다항식의 차수와 관계 없이 무조건 $2^{17}$으로 생각한다. 

그러면 NTT는 다항식 $f$가 주어지면 $f(w^0)$부터 $f(w^{2^{17}-1})$을 제공한다. 단, $w=t^6$이며 $t$는 원시근.

그러니 보통 우리의 요령은 각 $k-1$개의 다항식을 NTT하고, 그 결과를 pointwise 곱한 다음 역 NTT를 얹는 것이다.

그런데 이제 다항식이 바뀐다. 다행인 점은, 쿼리마다 다항식이 $k-1$개 중 하나만 바뀌고, 조금만 바뀐다는 것이다.

애초에 바뀌는 양이 단항식 하나라서, $f$ 값을 $\mathcal{O}(2^{17})$ 시간에 바꿔줄 수 있다.

또한, 바뀐 후의 pointwise 곱 역시 해당 위치 $k-1$개의 값 중 $0$의 개수 등을 관리하면 효율적으로 계산할 수 있다.

이렇게 하면 $g$ 값이 뒤집힌 이후에도 pointwise 곱 결과가 얼마인지를 빠르게 관리할 수 있다.

이제 이 결과를 전부 합친다음, 역 NTT를 하자. 여기서 NTT가 선형사상임을 이용하였다. 이러면 끝. 나쁘지 않다.  

카탈란 문제니까 카탈란처럼 접근하자. $n$각형에서 빨간색 영역의 개수의 총합을 $f(n)$, 파란색 영역의 개수의 총합을 $g(n)$이라 하자.

$P_1P_2$가 속한 삼각형이 $P_1P_2P_k$라고 하자. 이 영역은 빨간색이 될 것이며, 양쪽은 $k-1$각형, $n-k+2$각형이 된다.

그러니 이때 추가되는 빨간색 영역의 개수는 $C_{k-3}C_{n-k} + C_{k-3} g(n-k+2) + C_{n-k} g(k-1)$이 된다.

이를 정리하면 $f(n) = \sum_{k=3}^n \left( C_{k-3}C_{n-k} + C_{k-3}g(n-k+2) + C_{n-k}g(k-1) \right) = C_{n-2} + 2 \sum_{k=0}^{n-1} C_k g(n-1-k)$가 된다. 

비슷하게 $g(n) = 2 \sum_{k=0}^{n-1} C_k f(n-1-k)$가 성립한다. 매우 생성함수가 필요해보이는 식이다.

그런데 그 전에 주의가 필요하다. 이 식만 보면 $f(2)=1$인데, 실제로는 $f(2)=0$이다. (index 문제) 나머지는 문제가 없다.

카탈란 수에 대한 생성함수를 $T(x)$, $f$에 대한 생성함수를 $F(x)$, $g$에 대한 생성함수를 $G(x)$라 하자.

여기서 우리는 $F(x) + x^2 = x^2 T(x) + 2 x T(x) G(x)$, $G(x) = 2xT(x)F(x)$가 성립한다. 

정리하면 $F(x) + x^2 = x^2T(x) + 4x^2T(x)^2 F(x)$가 성립하고, 결론적으로 $F$를 얻는다.

이를 실제로 계산하려면 $T(x)$를 어느 정도 계산하고, 다항식의 inverse를 계산하는 방법을 적용해야 한다.

이는 다항식 나눗셈 및 multipoint evaluation 등에 활용되는 부분이므로, 알아두는 것도 좋다.

다른 풀이로는 식의 형태를 보고 online FFT 각을 재서 푸는 방법이 있으며, 이 풀이가 정해였다고 한다. 18743번 참조. 

생성함수로 이렇게 풀리는 이상 polynomial coefficient의 recurrence가 존재할 것 같다. 실제로 존재한다. 얘 참고.

그래서 루트, 로그제곱 (online FFT), 로그 (생성함수 계산), 선형 (recurrence 유도) 풀이가 모두 있는 문제가 된다.

이제부터 급수 $f(x)$의 $x^n$의 계수를 $f(x)[x^n]$이라고 표기하도록 하겠다.

이 문제도 생성함수로 접근한다. 그 근거는 convolution에 있는데, 이걸 진짜 convolution으로 생각하면 너무 힘들다.

그냥 생성함수를 생각한 후, 그 함수를 $k$승한 뒤 계수의 부분합을 구하라는 문제로 받아들이는 것이 편하다.

이제 $b_m(n)$의 생성함수를 생각하자. 이는 결국 $(1+x+x^2+ \cdots )(1+x^m+x^{2m}+\cdots) \cdots$와 같다.

그러니 이를 정리하면 $\displaystyle \prod_{t=0}^\infty \frac{1}{1-x^{m^t}}$를 얻는다. 이제 본격적인 풀이를 준비하자. 어쨌든 목표는 $\displaystyle \sum_{i=0}^n \left( \prod_{t=0}^{\infty} \frac{1}{(1-x^{m^t})^k} \right)[x^i]$가 된다.

문제를 오히려 더 어렵게 만들어보자. 다항식 $P$가 있을 때, 이런 계산을 할 수 있다. $$\sum_{i=0}^n P(i) \cdot \left( \prod_{t=0}^{\infty} \frac{1}{(1-x^{m^t})^k} \right)[x^i] = \sum_{i=0}^n P(i) \cdot \sum_{j=0}^i \left( \frac{1}{(1-x)^{k-1}} \cdot \prod_{t=1}^{\infty} \frac{1}{(1-x^{m^t})^k} \right)[x^j]$$

$$= \sum_{j=0}^n \left( \sum_{i=j}^n P(i) \right) \cdot \left( \frac{1}{(1-x)^{k-1}} \cdot \prod_{t=1}^{\infty} \frac{1}{(1-x^{m^t})^k} \right)[x^j]$$

$$= \sum_{i=0}^n P^{*}(i) \cdot \left( \frac{1}{(1-x)^{k-1}} \cdot \prod_{t=1}^{\infty} \frac{1}{(1-x^{m^t})^k} \right)[x^i]$$  

여기서 $P^{*}$는 $P^{*}(i) = P(i) + P(i+1) + \cdots + P(n)$이 각 $0 \le i \le n$에 대해 성립하는 다항식이다. 

우리는 $P$를 $P^{*}$로 바꾸는 과정에서 $\displaystyle \frac{1}{1-x}$ 항을 하나 털었다. 이걸 $k$번 반복하면,

$$\sum_{i=0}^n P^{*k}(i) \cdot \left( \prod_{t=1}^{\infty} \frac{1}{(1-x^{m^t})^k} \right)[x^i] = \sum_{i=0}^{\lfloor n/m \rfloor} P^{*k}(m \cdot i) \cdot  \left( \prod_{t=0}^{\infty} \frac{1}{(1-x^{m^t})^k} \right)[x^i]$$

이제 우리는 $P$를 $P^{*k}$로 바꾸면서 ($k$번 적용했다는 뜻이다) $n$을 $\lfloor n/m \rfloor$으로 털었다.

결국 이 과정을 $n=0$이 될 때까지 진행하면 된다. $P$를 $P^{*}$으로 바꾸는 과정을 효율적으로 하기만 하면 된다.

이는 Faulhaber's Formula 등을 통해서 할 수 있다. 적당히 뇌를 써서 효율적으로 하면 여유롭게 통과된다.

두 발판 사이로 이동할 수 있는 시각은 $A \pmod{B}$ 형태의 값을 갖는 자연수들이 된다.

각 위치에 대해서 "그 위치를 지나는 발판"의 집합을 std::vector 등으로 관리하면, 이 시각들을 전부 전처리할 수 있다.

이 과정에서 중국인의 나머지 정리가 사용된다. 이제 다익스트라를 사용하는데, "특정 발판에 올라올 수 있는 최소 시각"을 보면 된다.

다른 풀이가 있는 것으로 아는데, 중국인의 나머지 정리 템플릿이 있으면 이 풀이가 더 쉬운 것 같다.

$F_K^1$, $F_K^2$, $F_K^4$ 등을 손으로 계산해보면 핵심적인 패턴을 찾을 수 있다. 

결국 이진 거듭제곱과 같은 계산과 함께, 부분합을 계산하여 풀 수 있는 문제가 된다. 

구현이 조금 귀찮은 문제다. $2^t$를 간격으로 하는 부분합을 구해야 하는데 여기서 사이클이 여러 개 생길 수 있어서다.

뭔가 오프라인 + 자료구조 같은 덜 수학적인 풀이가 있을 것 같지만, 나는 걍 수학으로 밀었다.

문제의 해결을 온라인으로 한다. 우선 답에 대해서 이분탐색을 할 수 있음을 알 수 있다.

이제 $a_m, a_{m+1}, \cdots , a_r$ 중에서 $x$와 서로소인 것이 존재하는지 판별하면 된다. 이를 위해서는

$$\sum_{i=m}^r [\text{gcd}(a_i, x)= 1] = \sum_{i=m}^r \sum_{d|\text{gcd}(a_i, x)} \mu(d)$$

$$= \sum_{d|x} \mu(d) \cdot \left( \sum_{i=m}^r [d|a_i] \right) = \sum_{d|x} \mu(d) \cdot (cnt_d(r) - cnt_d(m-1))$$

를 계산하면 된다. 여기서 $cnt_d(m)$은 $a_1, a_2, \cdots, a_m$ 중 $d$의 배수의 개수를 의미한다.

이 값은 약수를 전처리하고 특정 값의 배수의 위치를 std::vector에 저장하고 lower_bound를 쓰는 것으로 빠르게 계산할 수 있다.

이걸 그대로 짜면 애석하게도 TLE가 발생하고, 약수를 관리하는 과정에서 $\mu(d) \neq 0$인 것만 사용하면 AC.

식을 정리해보자. 우리가 계산하고자 하는 값은 결국에

$$\sum_{1 \le i \le n, 1 \le j \le m, \text{gcd}(i, j) \le a} \text{lcm}(i, j) = \sum_{g=1}^a \sum_{i=1}^{n/g} \sum_{j=1}^{m/g}  gij \cdot [\text{gcd}(i, j) = 1]$$

$$= \sum_{g=1}^a \sum_{i=1}^{n/g} \sum_{j=1}^{m/g} gij \cdot \sum_{d|\text{gcd}(i, j)} \mu(d)  = \sum_{g=1}^a \sum_{d=1}^{\text{min}(n, m)/g} \sum_{i=1}^{n/gd} \sum_{j=1}^{n/gd} gd^2ij \cdot \mu (d)$$

$$= \sum_{g=1}^a \sum_{d=1}^{\text{min}(n, m)/g} gd^2 \mu(d) \cdot \binom{ \lfloor n/gd \rfloor +1 }{2} \cdot \binom{ \lfloor m/gd \rfloor + 1}{2}$$

$$= \sum_{T=1}^{\text{min}(n, m)} \sum_{g|T, g \le a} T \cdot (T/g) \cdot \mu(T/g) \cdot \binom{ \lfloor n/T \rfloor + 1}{2} \cdot \binom{\lfloor m/T \rfloor + 1}{2}$$

$$= \sum_{T=1}^{\text{min}(n, m)} T \cdot \binom{ \lfloor n/T \rfloor + 1}{2} \cdot \binom{\lfloor m/T \rfloor + 1}{2} \cdot \left( \sum_{g|T, g \le a} (T/g) \cdot \mu(T/g) \right)$$

이제 문제를 해결할 수 있다. 기본적으로 $a$에 대한 조건이 없다면, 이는 $n/T$, $m/T$로 가능한 값이 적다는 점을 이용해서 구간을 나누고, 각 구간에 대한 $f(T) = \sum_{g|T} (T/g) \cdot \mu(T/g)$의 부분합을 미리 전처리하여 해결할 수 있다. 이러면 쿼리 당 루트 시간에 문제를 풀 수 있다.

문제는 $a$에 대한 조건이다. 이를 위해서, 쿼리를 오프라인으로 해결하자. 쿼리를 $a$ 기준으로 정렬한다.

이제 다시 $f(T) = \sum_{g|T, g \le a } (T/g) \cdot \mu(T/g)$라고 정의하자. 이제 잘 생각해보자.

$a$가 증가하면 $a$의 배수인 $T$에 대하여 $f(T)$의 값이 변한다. 조화수열을 생각하면 변화 횟수는 많지 않다.

맨 처음의 식으로 돌아가서, 우리가 계산해야 하는 것은 결국 특정 구간에 속한 $T$에 대한 $f(T)$의 값들의 합이다. 

그러니 결국 점 업데이트 + 구간 쿼리 문제가 되고, 이는 단순한 세그먼트 트리를 이용하여 해결할 수 있다.

수학 대회 기출에서 가져온 문제지만 어쨌든 좋은 문제는 맞는 것 같다. 다음 관찰을 순서대로 해야한다. 증명은 생략.

1. $S(x)$는 단사함수다. 이 문제는 Putnam 2013 A2 문제이기도 하다. 여기까지는 쉽다.

2. $S(x)$는 사실 자연수에서 소수가 아닌 자연수로 (즉 1 포함) 가는 전단사함수이다. 이건 조금 까다롭다.

3. 2를 증명하는데 중요한 관찰은 다음 사실이다. $x$가 소수가 아닌 자연수라 하자. $x = t_1 > t_2 > \cdots > t_k$가 있어 $t_1 \cdot t_2 \cdots t_k$가 제곱수가 되도록 하는 $t_k$의 최댓값을 $T(x)$라고 하자. 이 값이 잘 정의됨을 보이는 것은 어렵지 않다. 이때, $S(T(x)) = x$가 성립함을 보일 수 있다. 

결국 문제는 $y$가 소수인지 판별하고, 아니면 $T(y)$를 구하는 문제가 된다. 이제 이 문제와 비슷해진다.

이 문제의 근본적인 해결 방법은 소인수의 지수들의 홀짝성을 $\mathbb{F}_2$의 벡터로 보는 것이다.

답에 대해서 이분탐색을 하자. 그러면 $m, m+1, \cdots , y-1$의 이진 벡터를 선형결합하여 $y$의 벡터를 만들 수 있는지 판별하는 문제가 된다.

이를 위해서는 가우스 소거를 할 필요가 있는데, 여기서 중요한 관찰이 하나 더 필요하다.

어쨌든 $1000$ 이상의 소수를 2개 이상 가질 수는 없다는 것이다. 그러니 모든 벡터를 $1000$ 이하 소수 200개쯤에 대한 벡터와 "내가 특별히 가지고 있는 $1000$ 이상 소수 하나 (없을 수도 있음)"으로 보는 것이 좋다. 이 관찰로 시간복잡도를 획기적으로 줄일 수 있다.

이 점을 고려하면 가우스 소거를 매우 효율적으로 할 수 있으며, std::bitset으로 최적화를 하면 문제가 해결된다.

문제에서 등장하는 수열은 OEIS에도 있는 수열로, 레퍼런스를 보면 관련 문제가 수학 잡지에도 등장한 것으로 보인다.

정말 오랜만에 rated round를 쳤다. 앳코더나 코포나 레이팅이 변하는 라운드는 2018년 초 이후로 처음이다.

문제가 조금 별로였고, 그런 라운드만 잘 치는 나는 덕분에 나쁘지 않게 대회를 쳤다.

C, A를 빠르게 해결한 것에 비해 B, D가 느렸는데, 풀이를 빠르게 찾았지만 구현에서 뇌절을 한 것이 컸다.

15분을 남겼을 때 E small을 읽고 풀려고 했는데, 손을 놓아버린 것도 아깝다. E small까지는 풀었어야 했다고 본다. ㄲㅂ

• A : 어쨌든 중요한 것의 2, 5의 개수이므로 이것만 잘 따지면 된다. $cnt[a][b]$를 2가 $a$개, 5가 $b$개인 수의 개수라고 하면 된다. 중복 카운팅을 조심해서 처리하자. 파싱하는 게 가장 어렵고 귀찮은 개노잼 문제다. 예전에는 무슨 가우스 소거를 A에 내더니 뭔...
• B : $S$가 $T$로 갈 수 있는 필요충분조건은, (단, $S \neq T$ 가정) 우선 당연히 $|S| > |T|$이고, $T$의 길이 $|T|-1$ suffix가 $S$의 길이 $|T|-1$ suffix와 같아야 하며, $T$의 첫 글자가 $S$의 첫 $|S|-|T|+1$개의 글자에서 존재해야 한다. 이를 기반으로, 해시를 해서 문제를 해결할 수 있다. suffix의 hash와 대응되는 prefix에 존재하는 알파벳에 대하여 카운트를 늘려주면, 이를 통해서 답을 구할 수 있다. 이를 단순하게 하면 TLE가 발생하고, 실제로 관심이 있는 해시 값인 각 문자열 $S_i$의 길이 $|S_i|-1$ suffix의 hash에 대해서만 계산하면 통과된다. 모든 문자열을 뒤집고 Trie를 써도 된다.
• C : 곱셈을 덧셈으로 바꾸면 FFT가 가능할 것 같다. 이를 가능하게 하는 도구는 로그다. 근데 정수론 문제니까 그냥 로그말고 이산로그를 쓰면 된다. $P$의 값이 작으므로, 문제 없다. 원시근은 $2$를 쓰면 된다. 걍 개노잼...
• D : 개인적으로는 재밌게 풀었던 문제. 더 좋은 풀이가 많은 것 같으니 한 번 확인할 필요는 있겠다. 일단 $DP[i]$를 $i$에서 위로 올라가서 $1$까지 곱한 값이라고 하고, $IV[i]$를 $DP[i]$의 잉여역수라고 하자. 그러면 우리가 구해야 하는 값은 각 $1 \le i <  j \le L$에 대하여 $\frac{DP[L+i-1] \cdot DP[L+P[i]-1] \cdot DP[L+j-1] \cdot DP[L+P[j]-1]}{DP[LCA(L+i-1, L+j-1)] \cdot DP[LCA(L+i-1, L+j-1)/2] \cdot DP[LCA(L+P[i]-1, L+P[j]-1)] \cdot DP[LCA(L+P[i]-1, L+P[j]-1)/2]}$를 합한 값이다. 식이 어마어마하게 더러운데, 천천히 생각해보자. 우선 $i$를 고정하고, $LCA(L+i-1, L+j-1)$을 고정해보자. 이렇게 되면 가능한 $j$의 영역이 구간을 이루게 된다. 우리가 여기서 걱정해야 하는 것은 $DP[L+j-1]  \cdot DP[L+P[j]-1]$의 값과, $LCA(L+P[i]-1, L+P[j]-1)$의 위치이다. 그런데 $LCA(L+P[i]-1, L+P[j]-1)$의 위치를 고정하면, 원하는 $P[j]$의 위치도 일종의 구간이 된다. 그러니 결국 "$j$의 구간, $P[j]$의 구간이 주어졌을 때 그 안에서 $DP[L+j-1] \cdot DP[L+P[j]-1]$의 합을 구하라"는 문제가 된다. 이는 Persistent Segment Tree로 할 수 있다. 이러면 $2^H H^3$ 풀이가 완성되는데, 이를 최적화할 수 있다. 아까도 말했지만 $P[j]$의 구간에 따라서 LCA의 위치가 달라지는데, 이 구간이 이진트리 특성상 어마어마하게 깔끔하다. 그래서 사실 PST를 위에서부터 내려가는 것으로 $P[j]$의 구간에 따른 각 쿼리를 로그 시간에 전부 해결할 수 있다. 그래서 $H$ 하나가 빠지고 $2^H H^2$ 풀이가 나온다. 끝. 나의 경우 PST의 초기 크기를 단순히 $2^{17}$로 잡지 않고, $2^{H-1}$로 정확하게 잡는 것이 중요했다. 이걸 놓쳐서 디버깅이 힘들었다. 다이아 5 ~ 다이아 4 정도 되는 문제 같은데 그래도 시간 안에 해결했다는 점은 긍정적이다.
• E : 재밌어 보이는 문제인데, 먼 미래에 업솔빙을 하는 것으로...

우선 $x|y^2+a$, $y|x^2+a$란 조건은 $\text{gcd}(x, y)=1$과 함께 생각했을 때, $xy|(x^2+y^2+a)$라는 것으로 바꿀 수 있다.

이제 이는 수학 올림피아드 계에서는 유명한 비에타 점핑 테크닉을 쓸 수 있는 문제가 된다.

$x^2+y^2+a=kxy$가 성립한다고 하고, 이를 만족하는 $x+y$가 가장 작은 순서쌍 $(u, v)$를 생각하자. WLOG, $u \ge v$다.

그런데 생각해보면 $(u, v)$가 조건을 만족하면, $(kv-u, v)$ 역시 조건을 만족하고, 이때 $kv-u = (v^2+a)/u$다.

그런데 최소성의 조건에서 $(v^2+a)/u \ge u$가 성립하고, $v^2+a \ge u^2$을 얻는다. 

즉, $x^2+y^2+a=kxy$를 만족함과 동시에 $y^2 \le x^2 \le y^2+a$를 만족하는 $(x, y)$를 전부 구하면, 이 해들이 "기본해"가 된다.

이는 $a \le 10^5$이므로 약수를 전처리하고 lower bound 등을 잘 활용하는 것으로 후보군을 줄여서 잘 계산할 수 있다.

이제 이 "기본해"를 가지고 각 $a$에 대한 해를 전부 생성하고, std::vector에 저장하자. 

쿼리에 대답하는 것은 간단한 lower bound로 해결할 수 있다. 시간/메모리가 모두 빡빡해서 조심히 구현해야 한다.

식부터 세우자. $x$ 좌표의 차이가 $i$, $y$ 좌표의 차이가 $j$인 두 점 사이에 레이저를 쏘았다고 하자.

그러면 이때 드는 비용이 $A(\text{gcd}(i, j)+1) + B(i + j - 2 \text{gcd}(i, j))$임을 쉽게 유도할 수 있다.

즉, 구하고자 하는 값은 $\sum_{i=1}^n \sum_{j=1}^m 4(n+1-i)(m+1-j)((A-2B)\text{gcd}(i, j) + A + B(i+j))$다.

식을 정리하면, 결국 문제의 핵심 난이도는 $\sum_{i=1}^n \sum_{j=1}^m \text{gcd}(i, j)$를 계산하는 것이다.

여기서 $\text{gcd}(i, j)$ 대신 $i \text{gcd}(i, j)$, $j \text{gcd}(i, j)$, $ij \text{gcd}(i, j)$를 넣은 경우도 계산해야 한다.

전형적인 식 정리 방식을 사용한다. 먼저 $\text{gcd}(i, j)$로 예시를 보이고, 나머지는 결론만 제시한다.

$$\sum_{i=1}^n \sum_{j=1}^m \text{gcd}(i, j) = \sum_{g=1}^{\text{min}(n, m)} \sum_{i=1}^{n/g} \sum_{j=1}^{m/g} g [ \text{gcd}(i, j) = 1]$$

$$= \sum_{g=1}^{\text{min}(n, m)} \sum_{i=1}^{n/g} \sum_{j=1}^{m/g} g \sum_{d|i, d|j} \mu(d) = \sum_{g=1}^{\text{min}(n, m)} \sum_{d=1}^{\text{min}(n,m)/g} g \cdot \mu(d) \sum_{i=1}^{n/gd} \sum_{j=1}^{m/gd} 1$$

$$= \sum_{T=1}^{\text{min}(n, m)} \left( \sum_{d|T} \mu(d)  \cdot \frac{T}{d} \right) \cdot \lfloor \frac{n}{T} \rfloor \cdot \lfloor \frac{m}{T} \rfloor = \sum_{T=1}^{\text{min}(n, m)} \phi(T) \cdot \lfloor \frac{n}{T} \rfloor \cdot \lfloor \frac{m}{T} \rfloor$$

그러니 $\lfloor n/T \rfloor$, $\lfloor m/T \rfloor$가 가질 수 있는 구간의 개수가 적다는 점을 이용하여, 각 구간에 대한 $\phi$ 함수의 합을 차례대로 구해주면 충분하다. 이는 $f(x) = \phi(x)$, $g(x) = 1$, $(f * g)(x) = x$를 이용한 xudyh's sieve로 가능하다. 다른 식들도 마찬가지 방법으로 정리가 가능하고, 결국 $x \phi(x)$, $x^2 \phi(x)$의 부분합을 구하는 문제로 환원된다. 이들 역시 마찬가지 방법으로 xudyh's sieve를 사용하여 해결할 수 있다. 나름 전형적인 듯.

우선 집합의 크기부터 생각해보자. $2n$의 경우 $n+1$부터 $2n$을 뽑으면 $n$개를 확보한다.

$2n+1$의 경우 $n+1$부터 $2n+1$을 뽑으면 $n+1$개를 확보한다. 즉, "홀수의 개수"가 답이 됨을 알 수 있다.

특히, 모든 자연수는 홀수와 2의 거듭제곱의 곱으로 유일하게 표현이 가능하다. 

만약 두 자연수가 위 표현에서 같은 홀수 부분을 가진다면, 두 자연수는 집합에 같이 속할 수 없다.

그러므로, 우리는 실제 최대 집합 크기가 "홀수의 개수"와 같음을 비둘기집의 원리로 증명한 셈이다.

이제 홀수들을 차례대로 나열하자. 우리는 각각에게 적합한 2의 거듭제곱을 줘서, 집합이 조건을 만족하도록 하고 싶다.

이때, 합을 최소로 하고 싶으므로, 가능한 최소의 2의 거듭제곱을 주고 싶다. 이를 그리디하게 하자.

만약 $n$이라는 홀수에 2를 주지 않았다면, $n/3$에는 무조건 2를 줘야 한다. 이런 느낌으로 가자.

결국 이를 정리하면 테스트 케이스 당 로그 시간이 걸리는 풀이가 나온다. 증명은 나도 잘 모르겟다 ㅋㅅㅋ

식을 정리하면, 우리가 구하고자 하는 답은 결국 

$$3^n \cdot \sum_{0 \le a+b \le n} \frac{n!}{a! b! (n-a-b)!} \text{gcd}(a, b) = 3^n \cdot \sum_{g=1}^n \sum_{1 \le a+b \le n/g} \frac{n!}{(ga)! (gb)! (n-(ga+gb))!} \cdot g \cdot [ \text{gcd}(a, b) = 1]$$ $$= 3^n \cdot \sum_{g=1}^n \sum_{1 \le a+b \le n/g} \frac{n!}{(ga)! (gb)! (n-(ga+gb))!} \cdot g \cdot \sum_{d|\text{gcd}(a, b)} \mu(d)$$ $$= 3^n \sum_{g=1}^n \sum_{d=1}^{n/g} g \cdot \mu(d) \cdot \sum_{1 \le a+ b \le n/gd} \frac{n!}{(gda)!(gdb)!(n-(gda+gdb)!}$$ $$= 3^n \cdot \sum_{T=1}^n \left( \sum_{d|T} \mu (d) \cdot \frac{T}{d} \right) \cdot \sum_{1 \le a+b \le n/T} \frac{n!}{(Ta)!(Tb)!(n-(Ta+Tb))!}$$ $$= 3^n \cdot n! \cdot \sum_{T=1}^n \phi(T) \cdot \sum_{c=1}^{n/T} \frac{1}{(n-Tc)!} \cdot \sum_{a=0}^c \frac{1}{(Ta)!(T(c-a))!}$$

한편, 오른쪽 식의 형태는 convolution 형태를 띄고 있으므로, FFT를 이용하여 효율적으로 구할 수 있다.

모듈로가 일반적인 소수이므로, 루트로 쪼개는 트릭을 사용하여 계산하여야 한다. 이러면 끝.

우선 각 $m$에 대하여 답을 구한 다음 부분합을 취하면 되는 형태다. 아예 다 구하고 출력만 하라는 뜻이다.

또한, 각 $m$에 대한 답은 자명하게 (중국인의 나머지 정리) multiplicative 하다. 그러니 prime power에 대해서만 해결하자.

이 prime power가 홀수인 경우, 문제는 어렵지 않다. $(x+y)^2 \equiv a+2b$, $(x-y)^2 \equiv a-2b$이므로 $a+2b$, $a-2b$는 이차잉여이고, 역으로 이 조건만 만족하면 조건을 만족하는 $x, y$도 있기 때문이다. 그러므로 답은 해당 prime power에 대한 이차잉여의 개수를 제곱한 것이다. 

prime power가 2의 거듭제곱인 경우 상황은 조금 복잡하다. 작은 거듭제곱의 경우 brute force로 답을 구할 수 있고, 믿음의 Berlekamp-Massey 알고리즘으로 답을 전처리할 수 있다. 아예 하드코딩해도 된다. 이제 이를 합쳐서 답을 구하는 것은 쉽다. 벌레캠프 각을 너무 늦게 봐서 해결이 오래 걸렸다.

식을 또 열심히 정리해보자. 우리가 원하는 답은 결국 

$$\sum_{a/b \le c/d \le e/f, d \le n} [\text{gcd}(c, d) = 1] = \sum_{a/b \le c/d \le e/f, d \le n} \sum_{g| \text{gcd}(c, d)} \mu(g)$$ $$= \sum_{g=1}^n \mu(g) \cdot \sum_{a/b \le c/d \le e/f, d \le n/g} 1 = \sum_{g=1}^n \mu(g) \cdot \sum_{d=1}^{n/g} \left( \lfloor \frac{e}{f}d \rfloor - \lfloor \frac{a}{b}d \rfloor + [ b|ad] \right)$$  

이제 $\lfloor n/g \rfloor$로 가능한 값이 적으므로 xudyh's sieve로 $\mu$의 부분합을 빠르게 구하면 된다.

또한, $\sum_{k=1}^n \lfloor ak/b \rfloor$ 형식의 값을 빠르게 구해야 하는데, 이는 이 문제와 같다.

진짜 개고생을 해서 풀었기 때문에, 풀이를 간단하게 스케치만 남긴다. 생각의 과정만 담는 수준으로 적는다.

• 우선 $k$가 작다는 것이 핵심인 것으로 보인다. $n$ 자체는 문제 풀이에 영향이 거의 없어야 한다.
• 사실 $x(x+1) \cdots (x+k)$를 더하는 문제면 엄청나게 간단한 문제가 된다. $\text{lcm}$이 붙어서 문제다.
• 그러면 $x(x+1) \cdots (x+k) / \text{lcm}(x, x+1, \cdots, x+k)$를 생각해보자.
• 생각해보면, 이 값이 가질 수 있는 소인수는 전부 30 이하이다. 
• 또한, 이 값이 $2$를 얼마나 갖는지는 $x \pmod{32}$에 의해서만 결정된다. $3$의 경우 $\pmod{27}$이고 등등.
• 중국인의 나머지 정리로, 대략 $x \pmod{N}$에 의해서만 저 값이 결정된다. $N$은 대략 $10^{12}$ 스케일의 값.
• 이걸 전부 나열하면 $\mathcal{O}(Nk)$ 수준의 풀이가 나온다. 저 $N$이 문제인데, 약간 meet-in-the-middle 같다.
• 소인수를 두 그룹으로 나누고, 양쪽을 "잘 합치는" 방법을 생각해야 한다.
• 이게 생각보다 어려운데, 커팅도 많이 하고 알고리즘 자체도 생각해야 하고 수학도 많이해야 한다. 

Vertex Simple Cycle을 구성하기 위해서, 왼쪽의 점 몇 개에서 각각 간선 두 개를 선택하는 것을 반복하자.

왼쪽의 점을 순서대로 보면서 사이클을 구축하는데, 이 과정에서 여러 사이클 조각들이 (연결 컴포넌트) 만들어진다.

생각을 해보면 각 컴포넌트들은 어쨌든 완전한 사이클 하나이거나 (이 경우 답에 해당하는 사이클 하나를 얻는다) '일직선' 형태의 컴포넌트가 된다. 

이러한 컴포넌트를 연결하려면 끝점 두 개를 연결해야 한다. 기본적 아이디어는 이게 전부다.

이를 이용하여 동적 계획법을 할 수 있다. $dp[i][j]$는 왼쪽 $i$번째 점까지 고려했을 때, 컴포넌트가 $j$개인 경우의 수다.

식을 세우려고 해보면, 은근 중복 카운팅을 피하기가 어려움을 알 수 있다. 중복 카운팅을 피하기 위해서는 살짝 생각의 방식을 바꿔야 한다.

왼쪽의 점을 순서대로 보면서, 다음을 순서대로 한다고 생각해보자.

1. 이 점에서 '처음으로 도달 가능한' 오른쪽 점들이 있을 것이다. 이 중 사이클에 포함될 점들을 선택한다. 이들은 크기 1의 컴포넌트가 된다. 

2. 만약 그 점을 사이클에 포함할 것이라면, 간선 두 개를 긋는다. 이 두 간선으로 컴포넌트 두 개를 잇는다. 이때, 잇는 점은 컴포넌트의 끝점 중 하나다.

이러면 중복 카운팅이 없어짐을 알 수 있다. 이제 문제는 '컴포넌트의 끝점' 문제다.

컴포넌트의 크기가 1인 경우는, 끝점이 하나 존재하게 된다. 그래서 '컴포넌트의 끝점 두 개를 고르는 방법'에 대한 혼란이 온다.

이를 위해서는 그래프에 방향을 주면 된다. 모든 것을 방향 그래프로 보면, 들어가는 컴포넌트와 나가는 컴포넌트를 고르기면 하면 된다.

이제 컴포넌트의 크기가 1인 경우를 특별히 처리할 이유가 없고, 계산 마지막에 같은 사이클을 두 번 세는 것만 처리하면 된다.

우선 각 tuple에 대해서 게임이 독립적이므로, 각각의 Grundy Number를 구한 다음 XOR 하면 된다.

게임이 굉장히 복잡해보이는데, 사실 이 게임은 단순히 Nimber Multiplication에 대한 게임 해석이다.

그러니 실제로는 각 tuple에 해당하는 Nimber Product를 모두 XOR하면 된다. 

Nimber Field가 characteristic $2$임을 생각하면, 결국 주어진 행렬에서 determinant를 계산하라는 문제가 된다.

Nimber Multiplication이 꽤 시간이 오래 걸려서, 단순하게 가우스 소거를 하면 안되고 적당한 전처리를 해야 한다.

이 전처리의 구체적 내용은 Nimber Multiplication의 기본적 성질을 공부하면 파악할 수 있을 것이다. 찾아보는 것 추천.

RSK Correspondence에 대한 내용을 공부하면 (일단 증명은 공부 안했다 ㅠㅠ) 해결할 수 있다.

내용을 좀 읽다보면 굉장히 도움이 되는 내용을 찾을 수 있고, 그러면 문제를 Young Tableaux에 대한 것으로 바꿀 수 있다.

이제 문제는 Hook Length Formula 및 재귀를 통해서 해결할 수 있다. RSK는 제대로 한 번 봐야할듯.

이런 문제는 기본적으로 행렬로 표현하는 것이 도움이 많이 된다. 

전이행렬을 $M$이라고 하고 초기 확률분포를 $v$라 하면 $k$번의 움직임 후 확률분포는 $M^kv$가 된다.

그러니, 각 타겟에서 시행이 끝날 확률은 단순히 $v + Mv + M^2 v + \cdots$를 계산하여 얻을 수 있다.

수렴성이 보장되므로, $I+M+M^2 + \cdots = (I-M)^{-1}$을 사용할 수 있고, $(I-M)^{-1}v$를 구하면 된다.

이는 식 $(I-M)x = v$를 풀면 얻을 수 있다. 대응되는 matrix가 banded이므로, 효율적으로 가우스 소거를 하면 된다.

각 행에 영향을 주는 행이 위/아래 두 개 뿐이므로, 총 3개의 행에 대한 계수를 각 행에 대하여 저장하면 편하다. 

DP 식 자체는 간단하고, cost 함수인 $\displaystyle \sum_{i=1}^n \left( 1 + \lfloor \log_2 i \rfloor \right)$ 및 실제로 구하고자 하는 값이 $n$에 대하여 볼록함은 쉽게 추측할 수 있고 증명도 수학적 귀납법으로 어렵지 않다. 그런데 $n$ 범위가 $10^{15}$로 매우 높고, 아마도 출제자가 답이 long long int 범위를 넘어가도록 문제를 만들지는 않았을 것이므로, 답이 증가하는 폭이 꽤 작을 것이라고 유추할 수 있다. 즉, 실제로 답의 기울기가 변화하는 점이 적을 것이라고 생각하는 것이다. 이제 기울기가 변화하는 점을 이분탐색/삼분탐색을 잘 섞어서 찾아나가면 된다. 이 아이디어만 잡으면 그 뒤는 어렵지 않은데 아이디어 잡기가 굉장히 어려운 문제인 것 같다.

갓문제. 풀이는 월파 당시 어느 정도 스포를 당해서 100% 내가 생각한 풀이는 아니다. 다음 관찰을 순서대로 한다.

1. 만약 모든 주기가 서로소라면, 중국인의 나머지 정리처럼 생각하면 결국 각 신호등이 독립적이라고 봐도 무방하다.

2. 또한, 기본적으로 두 신호등이 있으면 순수히 그 두 신호등만 봤을 때 결과는 주기의 LCM을 주기로 갖는다.

3. 그러니 한 신호등의 주기가 다른 신호등의 주기의 배수라면, 두 개를 동시에 처리할 수 있다.

4. 조금 더 생각하면, 결과적으로 주기들이 모두 prime power인 경우에 문제를 효율적으로 풀 수 있다.

$T = 2520$이라하면, 각 $1 \le u \le 100$에 대하여 $u/\text{gcd}(u,T)$가 모두 prime power가 된다.

그러니, $t \in \{0, 1, \cdots T-1\}$을 보고, 시간대가 $t \pmod{T}$인 경우만을 생각하자.

이 경우, 각 신호등에 대한 결과의 주기가 위 관찰에 의해서 prime power가 되고, 문제를 효율적으로 풀 수 있다.

이걸 각 $t$에 대해 반복한 다음 결과를 합쳐주면 문제를 해결할 수 있다. $T$를 잡는 아이디어가 미친 것 같다.

박테리아의 위치와 방향을 하나의 노드로 생각하면, 박테리아의 움직임은 일종의 functional graph로 모델링할 수 있다.

이제 한 박테리아가 덫이 놓인 칸을 방문하는 것은, 방향에 따른 총 4개의 노드 중 하나를 방문하는 것과 같다.

박테리아는 각 노드를 아예 방문하지 않거나, 한 번 방문하거나, 첫 방문 후 주기적으로 (사이클의 길이에 따라) 방문하게 된다.

그러니 이 정보를 각 박테리아와 각 4개의 노드에 대해서 계산한 다음, 이를 합쳐주면 된다.

합치는 것은 기본적으로 중국인의 나머지 정리를 활용하되, 한 번 방문하는 경우를 조심하며 처리해야 한다.

또한, 실제 첫 방문 시간이 방문 주기보다 클 수 있다는 점을 유의해야 한다. 여러모로 구현에 조심할 게 많다.

다행히도 제한은 여유가 있어서 넉넉하게, 안전하게 구현해도 0ms AC를 받을 수 있다.

멋진 조합문제. 좌표압축이 굉장히 필요해보이는 문제다. 좌표압축을 하면, 각 구간은 사실상 "같은 성질"을 만족하는 값들로 구성되어 있다.

$dp[x][y]$를 $x$번째 사람까지 선택이 끝났고, 현재 선택한 최댓값이 속하는 구간의 번호가 $y$ 이하인 경우의 수라고 하자.

$x$번째 사람이 선택하지 않는 경우, 현재 선택한 최댓값이 속하는 구간의 번호가 $y$가 아닌 경우는 이전에 처리한 DP 값으로 계산할 수 있다.

이제 남은 건 $x$번째 사람이 선택하고, 선택한 최댓값이 속하는 구간의 번호가 $y$인 경우다.

중복 카운팅을 막는 최적의 방법은, "처음으로 $y$번째 구간에서 값을 선택한 위치"를 고정하는 것이다.

이를 $k$라고 하자. 그러면 우선 $k-1$번째 사람까지 선택한 최댓값은 $y-1$ 이하가 되고, $dp[k-1][y-1]$이 나온다.

또한, $k$번째 사람, $x$번째 사람은 $y$번째 구간에서 값을 선택해야 하며, 나머지는 자유다.

하지만, $k$번째에서 $x$번째 사람들이 선택한 값은 증가수열을 이루어야 한다.

$k$번째부터 $x$번째 사람 중 $y$번째 구간에서 값을 선택할 수 있는 사람의 수를 $t$라 하자. (단, $k, x$번째 사람은 제외)

그러면 이 경우 $k$번째부터 $x$번째 사람이 선택할 수 있는 값의 경우의 수는 얼마가 될까?

우선 $t$명 중 $i$명이 실제로 값을 선택한다고 하자. 그러면 $k, x$를 포함해서 $i+2$개의 값을 골라야 하고, 이들은 증가해야 한다.

$y$번째 구간의 길이가 $L$이라면, 결국 $\displaystyle \sum_{i=0}^t \binom{t}{i} \cdot \binom{L}{i+2}$가 원하는 값이 된다.

이는 Vandermonde's Identity를 생각하면 쉽게 계산된다. $\displaystyle \sum_{i=0}^t \binom{t}{i} \cdot \binom{L}{L-i-2} = \binom{t+L}{L-2} = \binom{t+L}{t+2}$를 얻는다.

$k=x$인 경우를 특별하게 처리해주면, 문제를 해결할 수 있다. 이항 계수는 적당히 잘 계산하자. $\mathcal{O}(N^3)$의 동적계획법이 완성된다. 

생성함수를 이용한다. 생성함수에 대한 식으로 답을 표현하는 게 상당히 귀찮다.

전형적인 포함-배제를 하듯이, 열심히 계수를 맞춰주면 되는데, 결론적으로 이런 식이 나온다. 검증해보자.

그러면 식이 대충 계산 가능한 다항식이 분자에 있고, $(1-x^t)$ 형태의 식이 분모에 있는 형태가 된다.

그런데 $\displaystyle \frac{1}{1-x} = 1+ x+x^2+ \cdots$를 이용하면 분모를 없애고 식 전체를 생성함수로 전개할 수 있다.

조금 머리를 굴리면, 댓글의 말처럼 뒤에 있는 네 개의 항을 $\mathcal{O}(n^3)$으로 단순 계산을 할 수 있음을 확인할 수 있다.

첫 번째 항인 $A(x)^4$가 약간의 문제가 된다. 이 경우 $\sum_{i=1}^n \left( x^{l_i} - x^{r_i+1} \right)$에 곱해지는 값은 $\displaystyle \frac{1}{(1-x)^4} = \sum_{k=0}^\infty \binom{k+3}{3} x^k$이다.

이제 $\displaystyle P(x) = \sum_{i=1}^n \left( x^{l_i} - x^{r_i+1} \right)$라 하고, 다항식 $f$의 $x^t$의 계수를 $[f]_t$라 하자.

우리가 구하고자 하는 값은 $\displaystyle \sum_{i=0}^s [P(x)^4]_i \binom{s-i+3}{3}$이다. 문제는 역시 $P(x)^4$를 구할 여력이 없다는 점이다.

이 문제를 Vandermonde's Identity로 해결할 수 있다. 우선 $\displaystyle [P(x)^4]_i = \sum_{j=0}^i [P(x)^2]_j [P(x)^2]_{i-j}$라고 써보자.

그러면 우리가 계산해야 하는 것은 $\displaystyle \sum_{i=0}^s \sum_{j=0}^i [P(x)^2]_j [P(x)^2]_{i-j} \binom{s-j-(i-j)+3}{3}$이다.

이제 저 이항 계수를 쪼개고 싶다는 게 명확해지고, $\displaystyle \binom{s-j-(i-j)+3}{3} = \sum_{l=0}^3 \binom{3-j}{l} \cdot \binom{s-(i-j)}{3-l}$로 이를 쪼갤 수 있다.

식을 제대로 쪼개고 나면 문제가 크게 어렵지 않다. $P(x)^2$에 대한 정보를 전부 계산하고, 정렬/부분합이면 된다.

은근 상수도 커서 (특히 $\mathcal{O}(n^3)$ 부분이 조금 상수가 크다) 구현을 나름 섬세하게 해야 했다.

이 문제의 핵심 아이디어는, 첫 줄에 대한 press/avoid를 결정하면, 나머지는 전부 자동적으로 결정된다는 것이다.

첫 줄을 모두 결정하면, 두 번째 줄은 첫 줄을 맞춰주기 위해서 자동 결정이고, 세 번째 줄은 두 번째 줄을 맞춰주기 위해서 자동 결정이다.

이를 반복하면, 결국 모든 줄이 자동적으로 결정된다. 이때, 우리의 목표는 이때 마지막 줄이 정확하게 완성되는 것이다.

다른 말로 하면, "가상의 마지막 줄"을 하나 더 추가하고, 이들을 전부 avoid 하는 것이 "자동 결정되도록" 하는 것이다.

어쨌든 이를 전부 식으로 쓰면, $\mathbb{F}_2$ 위의 linear equation을 하나 얻을 수 있다. 

이건 가우스 소거 + bitset으로 쉽게 해결할 수 있고, 답 복원도 위 원리를 파악했다면 쉽게 할 수 있다.

구현 디테일이 조금 귀찮은데, $H > W$가 되도록 직사각형을 돌려줘야 한다. 가우스 소거가 $\mathcal{O}(W^3)$에 작동하기 때문이다.

또한, 기본적으로 각 칸의 press/avoid 여부를 첫 줄의 press/avoid 여부의 선형결합으로 표현하는데, 이 과정에서 토글링이 필요하다.

이 문제에서 조금 더 나아가면 Project Euler 707번을 해결할 수 있다. 물론 더 머리를 써야하는 문제다.

아이디어 3개로 문제를 해결할 수 있고, 다른 풀이들도 대부분 이런 방식으로 생각하는 것 같다.

아이디어 1: Bounding Box의 크기는 한 번의 시행마다 양변의 길이가 2만큼 증가한다. 오류 여부는 상관없다.

아이디어 2: 오류가 없는 경우, 시행 이전에 모습을 복원하는 것은 간단한 DP로 어렵지 않게 할 수 있다.

아이디어 3: 오류가 있는 경우, 위 방식대로 복원을 하면 오류가 어떻게 전파되는가를 그려볼 수 있다.

그림을 실제로 그려보면 오류의 존재 여부 및 오류의 위치를 파악하는 방법을 알 수 있다.

또한, 오류의 위치를 알 때 오류를 수정하는 방법 역시 쉽게 파악할 수 있다. 

만약 오류를 수정해도 여전히 오류가 있다면, 그때는 "시행 이전의 모습" 자체가 없었던 것으로 보면 된다.

이제 남은 건 구현이다. 진짜 재밌고 멋있는 문제라고 생각하고, 17WF 남은 문제도 풀어봐야겠다. 

정말 재밌게 푼 문제다. 깔끔하고 아이디어도 좋은 문제. 이 문제는 풀이만 써놓기엔 좀 애매해서 생각 과정도 적는다.

Part 1: 기본적인 관찰

결국 문제의 statement는 각 문제에 대한 아이디어는 시작 후 $0, 1, \cdots t-1$분 후 중 한 시각에 얻어지고, 각 확률이 $1/t$로 동일하며 이는 문제마다 독립적이라는 것이다. 이는 $p \cdot t^n$이 정수인 이유가 되고, 동시에 이 문제가 확률 문제가 아닌 카운팅 문제임을 시사한다.

Part 2: $n$이 작은 경우 직접 계산

우선 $x_1+x_2+ \cdots + x_n > t$인 경우에 답이 $0$임은 자명하다. $n=1$인 경우 답이 $t-x_1+1$임도 자명하다.

$n=2$인 경우를 열심히 계산했고, (이 계산은 어렵지 않다) $(t-x_1-x_2+1)(t-x_2+2)$를 얻었다. 

이는 문제의 답이 생각보다 간단한 형태를 가질 거라는 믿음을 나한테 줬다. 도움이 꽤 된듯.

Part 3: $n = t$, $x_1 = x_2 = \cdots = x_n = 1$인 경우

예제 2가 이런 경우고, $n=5$였다. 이때 예제 답이 $1296$이었는데, 이건 $6^4$다. 

뭔가 느낌이 쎄해서 $n=2$, $n=3$인 경우를 손으로 계산했는데, 각각 $3^1$, $4^2$가 나왔다.

여기서 나는 답이 $(n+1)^{n-1}$이라고 확신했고, 증명을 고민하기 시작했다. 근데 생각해보니 아는 내용이었다.

이 경우에는 중간에 문제가 바뀌는 걸 고민할 필요가 없다. 시간 안에 아이디어가 공급되는 것만이 중요하다.

각 문제의 아이디어가 나오는 시간을 $t_0, t_1, \cdots , t_{n-1}$이라 하면, 정렬 후 $i$번째 값이 $i$ 이하이면 된다. (0-index) 

이건 Parking Function과 같은 문제고, 예전에 한 번 공부를 했다. 여기서 도움을 정말 많이 받았다.

Parking Function하면 역시 원으로 바꾸고 자리 하나 더 만드는 방법이 너무 강력해서, 이를 사용해보기로 생각했다.

Part 4: $x_1 = x_2 = \cdots = x_n = 1$인 경우

기존 Parking Function에서 한 방식과 마찬가지로, 총 $t$개의 타임슬롯에 하나를 추가하고 이를 원형으로 바꾸자.

정당한 시간 배치가 되려면, 추가된 타임슬롯을 사용하지 않으면 된다. 여전히 문제는 Parking Function과 다르지 않다.

문제 큐에서 대기하고 있는 것을 자리가 차지되어서 다음 자리로 넘어가는 것으로 생각하면 된다.

이제 임의로 각 문제의 아이디어가 생각날 시간을 고르고 (즉, 각 차가 선호하는 자리를 고르고) 그 중 추가된 타임슬롯이 비게 되는 경우를 세자.

전체 경우의 수는 $(t+1)^n$이고, 그 중 $(t-n+1)/(t+1)$ 만큼이 추가된 타임슬롯을 사용하지 않는다. 

여기서 기존 Parking Function에서 사용되는 rotation argument가 그대로 사용된다.

그러니 답은 $(t-n+1)(t+1)^{n-1}$이 된다. 이는 $t=n$인 경우 Part 3의 결과와 모순되지 않는다.

Part 5: 본 문제 해결

이제부터 본 문제를 해결해야 한다. 역시 하나의 타임슬롯을 추가하고 원형으로 문제를 바꿔보자.

역순으로, $n$번째 문제부터 순서대로 타임슬롯을 고른다고 하자.

$n, n-1, \cdots , k+1$번째 문제에 대응이 되는 타임슬롯을 골랐다고 하자.

추가한 각 문제가 (한 문제를 연속된 한 구간동안 잡는다는 조건 때문에) "금지하는" 타임슬롯의 개수를 생각해보자.

조금 생각해보면 실제로 금지하는 타임슬롯의 개수가 특정 값으로 고정된다는 것을 알 수 있다. 경우 나누기가 필요 없다는 뜻.

이제 순서대로 타임슬롯을 골라준 다음, 추가된 타임슬롯을 사용하지 않도록 회전해주면 된다.

여기서 실제로 타임슬롯을 고른다는 것의 의미가 무엇인지 헷갈릴 수 있는데, 이건 잘 생각해보자.

큰 그림은 꽤 뻔하지만, 디테일과 구현이 생각보다 까다로운 문제다.

큰 비트부터 보고, 그리디하게 가능하면 1이 XOR의 결과로 나오도록 하는 것을 반복해야 한다.

목표가 $x \in [a,b]$, $y \in [c,d]$에 대하여 $x \oplus y$의 supremum을 구하는 것이라고 하자.

우선, $a, b, c, d$ 각각에 $2^{-60}$을 곱해서 전부 $1$ 미만의 값이 되도록 하자. 나중에 $2^{60}$을 다시 곱하면 된다.

이제 $2^{-1}$에 해당하는 비트부터 시작해서, 큰 비트부터 차례대로 보자.

$a, b, c, d$가 현재 보고 있는 비트를 갖는지 여부를 $0/1$로 표현해보자.

$0000, 0011, 1100, 1111$의 경우에는 결정권이 없으니, 보고 있는 비트를 제외한 값으로 $a, b, c, d$를 대체한다.

$0001$의 경우에는 이 비트에서 XOR을 1로 만들어야 하므로, $y$의 비트를 $1$로 고정해야 한다. 이는 $c$를 교체하는 것과 같다.

$0100$의 경우에도 마찬가지로, $x$의 비트를 $1$로 고정해야 한다. 이는 $a$를 교체하는 것과 같다.

$1101$의 경우에는 $y$의 비트를 $0$으로 고정해야 하고, 이는 $d$를 교체하는 것과 같다.

$0111$의 경우에는 $x$의 비트를 $0$으로 고정해야 하고, 이는 $b$를 교체하는 것과 같다.

$0101$의 경우는 조금 특수한데, 조금 생각하면 이 경우에는 아예 답이 결정됨을 알 수 있다.

$1.000000$과 $0.1111111$을 XOR하면 사실상 가능한 최대의 값을 뽑아낼 수 있기 때문이라고 생각하면 쉽다.

이제 이를 반복해서 재귀적으로 계산하면 되는데, 문제는 이 과정이 무한히 반복될 수 있다는 것이다.

여기서는 $a, b, c, d$의 이진법 표기의 주기성을 이용하면 된다. 즉, 반복 주기가 되면 그 시점에서 재귀를 끊을 수 있다는 것이다.

이렇게 하면 풀이는 완성되는데, 생각보다 고려해야 할 것도 많고 구현도 힘들다. 디테일은 각자 채워 넣어보자. 

예전에 $\mathcal{O}(n^2)$ 논문이 있길래 이걸 구현해보려다가 뇌절을 심하게 하고 멘탈 나가서 놓은 문제였다.

풀이는 이 블로그에서도 언급한 EGZ 정리의 증명을 이용한다. 우선 합성수인 경우, 문제를 쪼개서 합칠 수 있다.

$n=ab$라 쓰자. 단, $a, b > 1$. $2ab-1$개의 수가 있을 때, $a$에 대한 문제를 여러 번 풀어 합이 $a$의 배수가 되도록 묶인 $2b-1$개의 그룹으로 만들 수 있다. $2a-1$개의 수를 가지고 합이 $a$의 배수인 그룹을 하나 만들고, 사용되지 않은 수를 다시 써먹는 것을 반복하면 된다.

이제 $2b-1$개의 그룹을 가지고 단순히 $b$에 대한 문제를 풀면 된다. 이는 구현이 귀찮지만 어렵지는 않다.

소수인 경우가 문제인데, 이는 여러 방법의 증명이 있다. (내가 좋아하는 것은 Chevalley-Warning) 

여기서는 Cauchy-Davenport 정리를 사용한다. 주어진 수를 정렬하여, $0 \le a_1 \le a_2 \le \cdots \le a_{2p-1} < p$라 하자.

이제 $a_i = a_{i+p-1}$인 $i$가 있다면 $i$부터 $i+p-1$을 전부 택하면 합이 자명하게 $p$의 배수가 된다.

그렇지 않다면, 주어진 수를 $\{a_1\}, \{a_2, a_{p+1}\}, \{a_3, a_{p+2}\}, \cdots, \{a_p, a_{2p-1} \}$로 분할하자.

첫 집합을 제외하면, 각 집합의 크기는 (중복 원소가 없으므로) $2$가 된다. 이제 순서대로 Cauchy-Davenport를 쓰면, 각 집합에서 한 원소를 골라서 $p$의 배수를 만들 수 있음을 얻는다. 이를 knapsack과 같은 방법으로 처리하면 끝. 참 멋진 문제라고 생각한다.

위 문제의 구현을 bitset 등으로 최적화하면 맞는다. 이상한 실수를 하나 해서 시간을 오지게 날렸다.

Online FFT 테크닉을 이용하여 해결할 수 있는 문제다. 여기서는 이 테크닉을 간단하게 설명한다.

배열 $a$가 주어져 있고, 이때 $c_i = \sum_{j=0}^i a_j a_{i-j}$를 구하고 싶다고 하면, 단순히 FFT를 적용하면 된다.

그런데 만약 $a_i$가 $c_i$와 관련된 값이라던가, 배열 $a$가 바로 주어지지 않고 online으로 주어지면 어떻게 될까?

이때는 단순한 FFT로는 해결하기가 어려우나, 분할 정복을 추가하여 해결할 수 있다.

여기서는 설명의 간단함을 위해 $a_0=0$이라고 가정하고, $c_i = \sum_{j=1}^i a_j a_{i-j}$를 계산해야 $a_i$를 얻을 수 있는 구조라고 생각하자. 

카탈란 수의 점화식을 순수하게 FFT 하나로 계산한다고 생각하면 편할 것 같다.

$[L, R)$에 대해서, 문제를 해결하는 재귀함수 $f([L, R))$을 생각해보자. 이때 기본 가정은, 각 $L \le x < R$에 대하여 $a_0, a_1, \cdots, a_{L-1}$의 값을 이미 알고 있으며 각 $L \le t < R$에 대해 $p_L(x)^2 = \left( \sum_{i=0}^{L-1} a_i x^i \right)^2$의 $x^t$ 계수를 저장해놨다고 가정한다.

먼저 $M=(L+R)/2$를 잡고, $f([L, M))$을 호출하자. 이제 $f([M, R))$을 호출할 준비를 해보자.

현재 저장해놓은 $M \le t <R$에 대한 $p_L(x)^2$의 $x^t$의 계수들을 $p_M(x)^2$의 $x^t$의 계수들로 바꿔야 한다.

이는 결국 $(p_M(x)-p_L(x))(p_M(x)+p_L(x))$의 $x^t$ 계수를 구하는 것과 마찬가지다.

$p_M(x)-p_L(x)$는 $L$차 이상 $M$차 미만 단항식들로 구성되어 있다. 또한, 구해야 하는 계수는 최대 $R-1$차이다.

그러니, $p_M(x)+p_L(x)$의 $R-1-L$차 이하 단항식들만 고려해도 충분하다. 그러니 곱해야 하는 두 다항식의 실질적인 차수는 $R-L$에 비례한다. 개인적으로는 $L=0$인 경우를 따로 고려하는 것이 마음이 편하다. 어쨌든 정복 단계라고 볼 수 있는 스텝이 FFT로 $\mathcal{O}((R-L)\log(R-L))$에 된다.

그러니 총 시간복잡도는 $\mathcal{O}(N \log^2 N)$이 된다. 로그 하나는 순수한 분할정복에서 나오므로 꽤 빠르다.

식을 조금만 정리해보면 $x_p$가 굉장히 간단한 형태로 나온다는 것을 알 수 있고, 이를 통해서 $p$의 값의 후보를 얻는다.

답을 구하는 것도 매우 쉬운데, 특별한 시간 제한 때문에 Ruby 2.7 등의 언어를 사용해서 문제를 해결해야 한다.

Ruby 2.7 문법을 배우는 것이 시간이 꽤 오래 걸릴 것 같았는데, 요구하는 연산이 간단해서 다행이다.

각 숫자가 등장하는 위치를 모두 vector로 들고 있으면, 각 사람에게 돌을 추가해야 하는 시점이 언제인지를 빠르게 구할 수 있다. 

물론, 이를 전부 naive하게 계산하면 TLE가 나고, 메모이제이션을 하면서 계산하면 된다. 

즉, 특정 돌 개수에서 특정 턴일 때 몇 개의 돌이 추가되는지를 메모이제이션을 하면서 계산한다. 

상태의 개수가 꽤 작다는 점은 직관적으로 이해하긴 했는데, 가장 쉽고 명확하게 설명할 수 있는 방법이 뭔지는 아직 잘 모르겠다.  

이 문제와 매우 비슷한 형식을 가지고 있는 문제다. 마찬가지로 포함배제를 사용해보자. 편의상 $v_i = b^i - c + 1$이라고 쓴다.

그러면 식이 $\displaystyle \sum_{S \subset \{1,2, \cdots n\}} (-1)^{|S|} \binom{m+n-1-\sum_{i \in S} v_i}{m}$임을 쉽게 확인할 수 있다. 여기까지는 링크의 문제와 같다.

보통 이런 식이 나오면, $\sum_{i \in S} v_i$에 대한 다항식으로 이항계수를 생각하고 싶다.

그런데 여기서는 조합적 해석의 특성상, $a<b$에 대하여 $\binom{a}{b}$를 다항식의 값이 아니라 $0$으로 봐야 한다.

이걸 다루기가 꽤 까다로운데, 앞선 문제에서는 이를 meet in the middle 방식으로 해결했다.

여기서는 $v_i$의 특수한 형식 - 즉 지수적으로 증가하는 형태 - 를 극단적으로 활용할 수 있다.

$dp[i][j][k]$를 $\sum_{S \subset \{1,2, \cdots , i\}, |S|=j} \left( \sum_{t \in S} v_t \right)^k$라고 정의하자. 이는 식을 열심히 전개하여, $\mathcal{O}(m^4)$에 전처리를 할 수 있다. 

이제 $\sum_{i \in S} v_i \le m+n-1$인 집합 $S$에 대해서만 다항식의 합을 계산해야 한다. 이는 Digit DP를 하듯이 계산할 수 있다. 

큰 "비트"부터 내려가면서, 지금까지 뽑은 것을 봤을 때 나머지를 "자유롭게" 뽑을 수 있다면, 전처리한 DP 값을 활용하여 답을 구할 수 있다. 

여기서 $v_i$의 지수적 증가를 활용한다. 전체적으로 문제는 $\mathcal{O}(m^4)$ 시간에 해결되며, 이는 PyPy3으로도 충분히 빠르게 돈다.

$n/2$ 초과 $n$ 이하 소수와 $1$은 쌍을 찾을 수 없고, 나머지는 쌍을 만들 수 있음을 쉽게 확인할 수 있다.

그러니 문제의 답을 구하기 위해서는 $n$ 이하의 소수 개수를 빠르게 계산할 수 있으면 된다.

나는 Lucy-Hedgehog 방식을 사용하는데, 이게 생각보다 꽤 느려서 Meissel-Lehmer를 새로 배웠다.

Codeforces Educational Round에 있는 Four Divisors 문제에서 가장 빠른 코드들을 많이 참고했다. 

Lucy-Hedgehog 방식이 기본적으로 $\mathcal{O}(N^{3/4})$고, 최적화하면 $\mathcal{O}(N^{2/3})$인데 최적화된 버전을 한 번 구현할 필요를 느낀다. 

우선 $x=1$을 따로 처리하고, 양변에 $x-1$을 곱해서 $x^m-1$에 대한 생각을 해보자.

이제부터 $x^m \equiv 1$이라 생각할 수 있으니, 고려해야 하는 다항식을 $m-1$차 다항식으로 변환할 수 있다.

이제 $x^m-1$이 $\sum_{i=0}^{m-1} c_i x^i$의 약수가 되는 $x$를 모두 구해야 한다.

물론, 모든 $c_i$가 $0$이라면 답은 무한하므로 $-1$을 출력해준다.

$x$진법처럼 생각하면, $x > \operatorname{max}|c_i|+2$인 경우 주어진 식은 해를 가지지 않는다.

그러니 각 $x \le \operatorname{max}|c_i|+2$인 경우에 대해서 판별을 빠르게 해주면 된다.

$x$를 고정하면, 다음과 같은 방식으로 다항식을 simplify 하는 아이디어를 생각할 수 있다.

$c_i \ge x$가 있다면, $x \cdot x^i$를 $x^{i+1}$로 바꿔준다. 즉, $c_i$에서 $x$를 빼고 $c_{i+1}$에 $1$을 더한다.

$c_i \le -x$가 있다면, $x \cdot x^i$를 $x^{i+1}$로 바꿔준다. 즉, $c_i$에서 $x$를 더하고 $c_{i+1}$에 $1$을 뺀다.

여기서 $x^m \equiv 1$도 활용한다. 한 번의 simplification에서 $\sum_{i=0}^{m-1} |c_i|$가 $x-1$만큼 감소한다.

초기 $\sum_{i=0}^{m-1} |c_i|$의 값은 $\mathcal{O}(N)$이므로, 이 과정은 $\mathcal{O}(N/x)$번 반복된다.

이제 simplify가 된 상황에서는 판별이 간단하다. 모든 $c_i$가 $0$이거나, $x-1$이거나, $-x+1$이어야 한다.

이 과정을 효율적으로 하려면 std::map, std::set 등을 든든하게 활용하고, 모든 연산을 rollback 하기 위한 stack도 관리해야 한다.

풀이를 내는 것보다 진짜 구현하는 게 훨씬 더 귀찮았던 문제였다. 다행히 시간제한은 여유있는 문제인듯.

이 글에 나온 이상한 공식을 사용한다. 답이 생긴 게 굉장히 resultant 느낌이 나게 생겼다.

또한, 다뤄야 하는 다항식들은 Chebyshev 다항식의 형태를 가질 것을 예측할 수 있다. 

실제로 이 아이디어는 맞고, Chebyshev 다항식이 갖는 다양한 성질들을 이용해서 잘 계산하면 답을 얻는다.

처음에 행렬곱을 생각해 쿼리당 $\mathcal{O}(n^3 \log m)$을 짜서 시간을 좀 많이 날려먹었다. 위 풀이는 쿼리당 $\mathcal{O}(n^2 \log m)$이다.

시간 제한이 워낙에 빡빡해서 Barrett Reduction 등 아는 모든 최적화 방법을 다 동원했다. 진짜 힘들었다....

귀찮고 쉬운 중국인의 나머지 정리 활용문제다. 벽을 기준으로 대칭시켜서 보는 것은 나름 well-known.

구현이 조금 귀찮은 면이 있는데, 이 문제에서는 $a, b$가 음수일 수 있고 서로소가 아닐 수 있음에 특별히 주의할 필요가 있다.

다항식의 거듭제곱을 빠르게 구하는 문제다. $Q = P^n$이면 $Q' = nP^{n-1}P'$이고 $Q'P = nQP'$을 얻는다.

이 식을 전개해보면, $Q$의 각 계수를 $Q$의 이전 계수에 대한 식으로 쓸 수 있음을 확인할 수 있다.

이를 naive 하게 구현하면 충분히 시간 안에 답을 얻을 수 있다. 최근에 관련 코포 글이 하나 올라왔는데 읽어봐야겠음.

감동적으로 좋은 문제. 우선 많은 XOR 문제가 그렇듯이, 비트로 쪼갤 생각을 해야 한다.

$m_1 \ge m_2 \ge \cdots \ge m_n$이라고 하고, $2^t \le m_1 < 2^{t+1}$이 성립한다고 하자. 특히, $m_1$부터 $m_k$가 $2^t$ 이상이고, 나머지는 $2^t$ 미만이라고 하자.

우리는 기본적으로 $2^t$ 비트를 짝수개 뽑아야 한다. $1 \le i \le k$인 $i$에 대하여, $i$번째 변수에서 $2^t$를 뽑는다면 그 변수의 범위는 $2^t$에서 $m_i$가 된다. 

그렇지 않는다면, $i$번째 변수는 $0$부터 $2^t-1$까지를 아무거나 뽑아줄 수 있다. 이는 굉장히 강력한 조건이며 이 문제의 핵심이다.

만약 $1 \le i \le k$ 중 $2^t$를 뽑지 않는 $i$가 있다면, 그 $i$를 제외하고 다른 변수들이 $2^t$ 비트만 제대로 맞춰주면 전체 XOR이 $0$이도록 $i$번째 변수의 값을 유일하게 결정할 수 있기 때문이다. 이를 생각하면, "처음으로 $2^t$를 뽑지 않는 index $i$"를 기준으로 카운팅을 해서 답을 얻을 수 있다.

만약 모든 $1 \le i \le k$에 대하여 $2^t$를 뽑는다면, $k$는 짝수여야 하며, $2^t$ 비트를 모두 제거했다고 가정하고 더 작은 문제를 해결하면 된다. 

가장 직관적인 접근은 역시 "가성비가 좋은 것을 많이 쓰자"다. 물론, 이게 안되니까 문제가 다이아 3이다.

하지만 이 직관은 전체적인 문제 해결에 정말 많은 도움을 준다. 

이 문제의 풀이를 쓰면 매우 길어질 것 같으니, 이미 풀이를 매우 잘 작성해주신 lego0901님의 블로그로 링크를 건다. 

중요한 것은 convex/linear 함수의 최댓값은 양쪽 끝에서만 발생한다는 사실이고, 이를 활용하는 직관이다.

(사실 난 lego0901님처럼 엄밀하게 증명하지 않고 대충 이러면 풀릴 거라고 믿고 짰다 ㅋㅋ)

우선 $N=K$이고 $N$이 홀수인 경우에 답이 없음은 정삼각형의 경우에서 직관적이고 증명하기도 어렵지 않다.

이제 본격적으로 construction을 생각해야 하는데, 같은 길이를 많이 만들어야 하니 $x^2+y^2 = T$의 해의 개수를 생각할 수 밖에 없다.

이는 $T$에 $4k+1$ 꼴 소수를 잔뜩 박아넣으면 되고, 대충 $T=5^4 \cdot 13 \cdot 17 \cdot 29 \cdot 37 \cdot 41 \cdot 53 \cdot 61$을 사용하면 된다.

이제 construction을 위해서는 길이가 $\sqrt{T}$인 벡터들을 몇 가지 모은 뒤, 이들을 각도정렬하여 만들면 된다.

몇 가지 주의사항이 있는데, $N$이 짝수인 경우에는 원점 대칭이 되도록 벡터들을 선택해야 한다.

또한, $N$이 홀수인 경우에는 $N-1$개의 길이가 $\sqrt{T}$이도록 만들면 되는데, 이 벡터들의 합이 $0$이 아니도록 해야 한다.

즉, 전부 원점 대칭이 되면 안된다. 또한, 첫 번째 길이가 $\sqrt{T}$가 되도록 적당히 점들의 순서를 회전할 필요도 있다.

마지막으로, 은근히 빡빡한 조건 중 하나인 좌표 범위 조건을 만족하기 위해 적당한 평행이동을 시켜주도록 하자.