rkm0959

$i$에 대한 답을 구하려면, $l \le i \le r$에 대하여 $\frac{\sum_{k=l}^r a_k}{r-l+1}$을 최대화하면 된다.

분수식의 최적화를 하려면 이분탐색을 쓰는 게 좋으니, 이분탐색을 걸어주자. $\frac{\sum_{k=l}^r a_k}{r-l+1} \ge x$인 $l \le i \le r$이 존재하는지 보자.

즉, $\sum_{k=l}^r (a_k-x) \ge 0$인 $l \le i \le r$이 존재하는지 확인하면 된다.

이를 위해서, $\sum_{k=1}^{l-1} (a_k-x)$와 $\sum_{k=r+1}^n (a_k-x)$를 각각 최소화하면 된다.

$f_{1, k}(x) = \sum_{i=1}^k a_i - kx$, $f_{2, k}(x) = \sum_{i=k}^{n} a_i - (n+1-k)x$를 정의하자.

$f_{1,1}(x), f_{1,2}(x), \cdots , f_{1, i-1}(x)$ 중 최소값을 구하고, $f_{2, i+1}(x), f_{2, i+2}(x), \cdots , f_{2, n}(x)$ 중 최소값을 구하면 된다.

이는 이 문제를 풀듯이 Segment Tree + Convex Hull Trick으로 해결할 수 있다. 기울기가 단조적임을 이용하자.

시간 제한이 많이 빡세서 여러 추한 최적화를 해서 맞았다. 사실 이게 정해가 아닌 것 같고 그냥 내가 뚫은 것 같다 ㅋㅋ

비벼서 푸는 것이 충분히 가능한 문제다. 증명하고 풀려면 조금 빡세다. Lifting The Exponent Lemma를 이용하면 된다.

문제 풀이의 시작에 대해 힌트를 조금 주자면, 먼저 답의 소인수는 $d$의 소인수여야 함을 보이자.

그 다음, $d$의 소인수 $p$를 잡고 $a$가 $p$의 배수인 경우와, 아닌 경우를 나누어서 위 보조정리를 적용해보자. 

주어진 $x \le y$에 대하여 가능한 최솟값을 먼저 $x, y$에 대한 식으로 구하면, $\lfloor \frac{x+y}{x+1} \rfloor$를 얻는다.

그 다음, 가능한 문자열의 개수를 동적계획법으로 구하면 된다. 이 과정에서 여러 최적화를 동원할 수 있다.

미리 "가능한 최솟값"을 기준으로 쿼리를 정렬해놓으면, 필요할 때마다 동적계획법을 돌려주면 된다. 

답 $k$를 고정했을 때, 가능한 $x$의 범위가 $x \le \frac{2n}{k}$이므로, 조화수열 형태의 시간복잡도를 얻는다. 

이 문제를 풀면 접근이 쉬워진다. $dp[S][c]$를 집합 $S$와 그 부분집합들을 모두 색칠하되, $S$를 $c$로 색칠할 경우 최소 비용이라고 정의하자. $S$를 빨간색으로 칠한다면, [$S$의 부분집합 중 파란색으로 칠해진 가장 큰 집합 $V$]은 유일하게 결정된다. (존재하지 않는 경우 포함) 이제 $V$에 존재하지 않는 원소를 갖는 $S$의 부분집합은 전부 빨간색으로 칠해지게 된다. 이를 이용하여, $\mathcal{O}(3^n)$ 동적계획법을 설계할 수 있다. 이를 최적화하려면, SOS DP를 활용하면 된다.

재밌는 문제였지만 AtCoder Quality인지는 잘 모르겠다 ㅋㅋ

키타마사법을 제대로 이해하고 쓰는지 묻는 문제다. 

키타마사법을 제대로 이해했다면, 문제를 단순한 가우스 소거법 문제로 변형할 수 있다.

Berlekamp-Massey 구현체와 (또는 키타마사 구현체) 대충 예전에 짜놓은 가우스 소거 구현체가 있으면 5분 안에 코드를 짤 수 있다.

선형대수학 문제니까 선형대수학 문제처럼 풀면 된다.

가우스 소거를 해야 하는데, 이걸 손으로 하기도 그렇고 코드를 짜기도 귀찮으니 Sage를 이용했다.

$\mathbb{Z}$를 ring으로 설정하고 가우스 소거를 해야지 각 $m$에 대해서 써먹을 수 있는 결과를 얻을 수 있음에 주의하자.

아무튼 열심히 계산을 시키고 패턴을 찾아보면 비벼서 풀 수 있다. 증명은 특별히 시도해보지 않았다.

트리의 Centroid를 생각하면 된다. 각 간선 $e$가 크기 $k, n-k$의 컴포넌트를 잇는다고 하자.

그러면 Centroid는 둘 중 크기가 큰 컴포넌트에 속하므로, 이 간선은 거리의 합에 $\operatorname{min}(k, n-k)$만큼 값을 더한다.

이제 대칭성을 극단적으로 활용해서, 1번 정점과 2번 정점 사이의 간선이 있는 경우, 그때 이 간선이 기여하는 값을 계산해보자.

1번 정점쪽의 컴포넌트 크기를 $k$, 2번 정점쪽의 컴포넌트 크기를 $n-k$라고 하자.

1번 정점쪽의 컴포넌트에 속하게 될 정점의 집합을 고르는 방법은 $\binom{n-2}{k-1}$개가 있다.

1번 정점쪽의 컴포넌트를 만드는 방법은 Cayley's Formula에 의해 $k^{k-2}$다. 

마찬가지로 2번 정점쪽 컴포넌트를 만드는 방법 역시 $(n-k)^{n-k-2}$다. 

이제 이 간선이 기여하는 값은 $\operatorname{min}(k, n-k)$다. 이제 이를 정리해서 계산하면 답을 얻을 수 있다.

그런디 넘버를 계산하면, 결국 $(a_1 \pmod {x+1}) \oplus (a_2 \pmod{x+1}) \cdots \oplus (a_n \pmod{x+1})$를 계산하는 문제가 된다.

$1, 2, \cdots , n$ 중 홀수번 등장하는 집합을 $S$라고 정의하자. $t(x+1) \le v < (t+1)(x+1)-1$인 $v \in S$에 대하여 $(v-t(x+1))$의 XOR 값을 로그 시간에 계산할 수 있으면, $\mathcal{O}(n \log^2 n)$에 문제를 해결할 수 있다. 이를 위해서, $\displaystyle f(i, 2^k) = \oplus_{i \le x < i+2^k, x \in S} (x-i)$라고 정의하자.

이 함수는 Sparse Table과 비슷한 방식으로 계산될 수 있고, 우리가 원하는 값들 역시 이를 이용하여 로그 시간에 계산할 수 있다. 

계산하는 과정이 굉장히 절묘하다. XOR의 성질과 Sparse Table의 성질이 절묘하게 잘 맞아떨어지는 것 같다.

Nim 게임의 결과는 XOR로 계산할 수 있다. 그래프의 Cycle 역시 XOR로 생각할 수 있다.

간선에 대응하는 벡터를 간선이 잇는 두 정점의 번호에 1, 나머지에는 0으로 두면 된다.

간선의 집합이 Cycle인 것은 간선에 대응하는 벡터들을 XOR하면 zero vector가 나오는 것과 같다.

Nim 게임에서 후공이 승리하는 것은 간선 위에 놓인 돌의 개수를 XOR하면 0이 나오는 것과 같다.

그러니 각 간선에 대하여 그 간선이 잇는 두 정점의 번호 및 간선 위에 놓인 돌의 개수에 대한 정보를 길이 $n+60$의 벡터로 만들 수 있다.

이제 good graph인 것은 결국 선택한 간선들에 대응되는 벡터들이 서로 선형독립인 것이다. ($\mathbb{F}_2$에서 본다)

결국 이 문제는 "maximum weight linearly independent subset"을 구하라는 문제다.

이 시점에서 구글 검색을 좀 해봤더니 대충 "matroid", "greedy" 같은 키워드가 나왔다. :(

어쨌든 이 문제는 그리디 알고리즘과 가우스 소거로 해결할 수 있다. 매트로이드를 한 번 공부해봐야 하나 싶다.

식 조작을 위해서 Iverson Bracket을 이용하겠다. 

각 $k$에 대해서 $c_k$를 구하는 문제를 풀자. 이제 index가 $k$의 배수인 값들만 보면 된다.

이제 $\text{gcd}(i, j)=1$, $1 \le i, j \le \lfloor \frac{n}{k} \rfloor$인 경우 $|a_{ik}-b_{jk}|$의 최댓값을 보면 될 것이다.

그러니 $c_1$을 빠르게 구하는 방법을 고안하면, 이를 이용하여 $c_1, c_2, \cdots c_n$을 전부 구할 수 있다. $c_1$을 구하자.

답에 대한 이분탐색을 하자. $|a_i-b_j| \ge C$인 $\operatorname{gcd}(i, j)=1$이 존재함을 판별하면 된다.

이를 위해서는 $X = \displaystyle \sum_{1 \le i, j \le n, |a_i-b_j| \ge C} \sum_{d|\operatorname{gcd}(i,j)} \mu(d) > 0$임을 판별하면 된다. 이는 $\sum_{d|n} \mu(d) = [n=1]$을 이용한 것이다. 

$i$를 고정하고, $a_i$가 $X$에 추가하는 값을 구하자. 그러면 $\sum_{d|i} \mu(d) \cdot \left( \sum_{j=1}^n [|a_i-b_j| \ge C] \cdot [d|j] \right)$가 $X$에 추가가 된다.

$\sum_{j=1}^n [|a_i-b_j| \ge C] \cdot [d|j]$는 결국 $|a_i-b_j| \ge C$이고 $d|j$인 $j$의 개수다.

$a_1, a_2, \cdots , a_n$을 정렬하고, $b_1, b_2, \cdots b_n$을 정렬하자. $a_i$의 기존 index를 $ida_i$, $b_i$의 기존 index를 $idb_i$라 하자. 

이제 $a_i$가 $X$에 기여하는 값을 $\sum_{d|ida_i} \mu(d) \cdot \left( \sum_{j=1}^n [|a_i - b_j| \ge C] \cdot [d|idb_j] \right)$로 다시 볼 수 있다.

이제 $|a_i-b_j| \ge C$를 만족하는 $j$는 구간 두 개로 나타낼 수 있다. 이 구간들은 $i$에 대하여 단조적이다.

그러니 투 포인터를 이용하여, $|a_i-b_j| \ge C$이고 $d|idb_j$인 $j$의 개수를 빠르게 계산할 수 있다.

모든 계산을 효율적으로 하기 위해서는 약수의 집합, 뫼비우스 함수의 값 등을 전처리해야 한다.

입시 대비할 때 비슷한 문제를 풀어서 빠르게 해결할 수 있었다. $D = \operatorname{min}(d_1, d_2, \cdots, d_n)$이라 하자.

시간 $x$에서 (단, $x \le D$) 아직도 버스를 타지 못했을 확률은 $P(x)=\prod_{i=1}^n \left( 1 -\frac{x}{d_i} \right)$다.

그러니 버스를 탈 시간에 대한 확률분포함수는 $-P'(x)$가 된다. 그러니 답은 $\int_0^D -xP'(x) dx$다. 

$P(x)$는 분할-정복 + FFT로 어렵지 않게 계산할 수 있다. 답을 저 형태로 구해도 되고, 부분적분을 해서 식을 $\int_0^D P(x) dx$로 변형한 다음 구해도 된다.

맨 처음에는 이 글 같은 걸 생각해서 뇌절을 열심히 했는데, 최근에 이 문제처럼 해싱하는 문제를 너무 많이 봐서 풀 수 있었다.

적당히 큰 소수 $P$를 잡자. $P \equiv 3 \pmod 4$이도록 잡아주면 더욱 좋다. $a_i \pmod P$를 계산하는 것은 쉽다.

이제 $\sqrt{a_i}$를 직접 다루는 대신, $x^2 \equiv a_i \pmod P$의 해 $x$를 $\sqrt{a_i}$라고 생각하자.

결국 $ \pm$를 적당히 잘 고르는 문제인 만큼, 해를 $x$, $-x$ 중 무엇을 생각하던 상관이 없다. 

$P \equiv 3 \pmod 4$이므로, $x^2 \equiv a_i \pmod P$를 빠르게 푸는 것은 어렵지 않다.

Tonelli-Shanks Algorithm을 돌려도 충분히 빠르게 결과가 나올 것이다. $v_2 (P-1)=1$이기 때문이다.

여기서 문제는 $x^2 \equiv a_i \pmod P$가 근이 없을 수 있는데, 이때는 $P \equiv 3 \pmod{4}$이므로 $x^2 \equiv -a_i \pmod P$가 근이 있다. 

이제 $\sqrt{a_i}$를 복소수 $x \cdot i$라고 생각하자. 이제 $\sqrt{a_i}$를 간단한 형태로 "구했다".

본 문제를 푸는 것은 간단한 meet in the middle 알고리즘으로 할 수 있다. 솔직히 왜 맞는지 모르겠다.

일반성을 잃지 않고, 주어진 그룹이 전부 1번 팀에 속하게 될 확률을 구해보자.

핵심 아이디어는 "처음으로 1번 그룹이 꽉차는 시점", "처음으로 2번 그룹이 꽉차는 시점"으로 경우를 나누는 것이다.

이걸 하면 간단한 조합론적 카운팅으로 식을 세울 수 있다. 문제는 이를 빠르게 계산하는 것이다.

식을 잘 세우면 결국 $\sum \frac{1}{2^k} \binom{k}{n-1}$와 주어진 사람의 수 $k_i$에 대하여 $\sum \frac{1}{2^k} \binom{k}{n-k_i-1}$을 주어진 $k$의 구간에 대하여 빠르게 계산해야 한다는 결론이 나온다. 

이 식을 빠르게 계산하는 방법은 잘 모르겠고 (식을 잘 조작하면 $\sum_{i=l}^r \binom{n}{i}$를 빠르게 계산하는 것과 동치다) 이 문제에서는 가능한 $k_i$의 종류가 대충 800개 이하이므로 (합이 20만 이하니까) 이를 이용해서 $\mathcal{O}(n \sqrt{\sum k_i})$로 문제를 해결할 수 있다. 여러모로 재미없는 문제였다. 구현이 좀 힘들었다.

조건이 무섭게 생겼는데, 이를 해석하면 각 연결 컴포넌트의 크기가 6 이하란 것이다. 귀류법으로 크기 7 이상인 연결 컴포넌트가 있다면, $A$를 적당히 잡아서 임의의 $a, b \in A$에 대하여 $A$에 속한 정점만을 통해서 $a$에서 $b$로 가는 경로가 존재하도록 할 수 있다. 그러니 모순을 얻는다.

그러니 각 컴포넌트의 채색다항식을 "상태 압축" 백트래킹 + Lagrange Interpolation으로 얻을 수 있다. Project Euler 194, 544를 참고하면 좋을 것 같다. 이제 답을 구해야 하는데, 정점의 개수가 6 이하인 그래프 중 서로 non-isomorphic한 것의 개수가 200개 정도니 200개 이하의 서로 다른 채색다항식 $p$에 대하여 $p(1), p(2), \cdots p(n)$을 naive하게 계산하면 된다. Project Euler에서 배운 것을 많이 써먹을 수 있었던 문제였다.

식의 성질을 찾으려고 너무 집착하다가 말렸다. 중요한 것은 식이 동차식이라는 것 뿐이다.

이 경우, $a=0$, $b=0$인 경우를 제외하면 중요한 것은 $a, b$ 자체가 아니라 $a \cdot b^{-1} \pmod{p}$만이 중요하다.

그러니 $a=0$이나 $b=0$인 경우를 먼저 처리하고, 조건을 만족하는 $a \cdot b^{-1}$의 값을 모두 구하자.

여기까지는 (역원을 미리 전처리한다면) $\mathcal{O}(p)$에 가능하다. 이제 각 $t$에 대하여 $a \cdot b^{-1} \equiv t \pmod{p}$인 $a, b \in S$의 개수를 빠르게 구하는 방법을 구하자. 양변에 "로그"를 취하면 이는 FFT로 해결할 수 있는 문제의 형태임을 알 수 있다. $\pmod{p}$ 합동식의 입장에서 로그를 취하는 방법은 원시근 $g$를 잡는 것이다. 이제 모든 것을 적당히 정리해주면 $\mathcal{O}(p \log p)$에 문제를 해결할 수 있다. 문제가 더러워 보이는 것을 제외하면 재밌었다.

식 형태가 convolution이고, 여러모로 상황이 XOR, AND, OR-convolution과 비슷하다는 것을 알 수 있다.

FWHT의 근본은 결국 비트별로 변수를 쪼갠다음 각 변수마다 적당히 convolution을 해서 합치는 것이다.

여기서도 비슷하게 할 수 있다. 하지만 convolution 각을 재기가 까다로운데, 기존 FFT, FWHT처럼 "다항식에 값을 대입한다"라는 생각보다는 행렬변환 -> 단순 "pointwise" 곱셈 -> 행렬변환을 통해서 convolution을 해야겠다는 생각을 해야하기 때문이다. 게다가 단순히 $0, 1, 2$의 개수를 가지고 식을 세우려 하면 터지고, 식을 하나 추가해야 convolution을 할 수 있는 형태의 식이 나오게 된다. 여러모로 빡센 문제. 코드는 FWHT에 살짝 변형을 주면 된다. 

그런데 FWHT처럼 구현했는데 맞는 이유는 솔직히 잘 모르겠다. 그냥 [각 "비트"별로 convolution을 하는 방법을 고안한 다음 FWHT처럼 짜면 되겠지]라고 생각해서 짰는데, 생각해보니까 FWHT는 multivariable polynomial처럼 생각하면 이해는 되는데 지금 하는 거는 그거랑은 또 달라서... 좀 생각해봐야 할 것 같다. 에디토리얼 찾아봐야 할 듯. Kronecker Product에 뭔가 큰 그림이 있는 것 같기도 하고 ㅋㅋ FWHT 구현 원리부터 다시 봐야겠다.

"Product of Finite Chain"을 최소 개수의 Chain으로 분할하라는 문제다. 

Dilworth's Theorem을 생각하면, 최대 크기의 antichain을 구하라는 문제다.

그런데 이 문제는 Romania TST 1997에서 (간단한 버전) 등장했고, Bruijn의 결과 역시 알려져 있다.

결국 $0 \le x_i < p_i$이면서 $\sum_{i=1}^n x_i = \lfloor \frac{1}{2} \sum_{i=1}^n (p_i -1) \rfloor$인 정수해의 개수를 구하면 된다.

포함-배제를 사용하면 $\mathcal{O}(2^n \cdot n)$ 풀이를 얻을 수 있다. 이는 당연히 비효율적이다.

하지만 meet in the middle 방식을 사용하면, 시간복잡도를 $\mathcal{O}(2^{n/2} n^2)$으로 줄일 수 있다. 

포함-배제 식을 제대로 세웠다면, meet in the middle을 통해서 최적화를 하는 과정은 복잡하지 않다.

이항 계수를 이항 계수로 보지 말고, 단순히 다항식으로 보면 도움이 많이 될 것이다.

예전에 koosaga 블로그에서 키워드 Berlekamp-Massey를 봐서 빠르게 풀 수 있었다. 그때는 내가 이걸 진짜 풀 줄 몰랐지...

$p_k$을 $k$번째 시행에서 처음으로 $n$번 정점에 도착할 확률이라고 하자. "처음으로"라는 조건을 그래프로 모델하려면, $n$번 정점에 도착하면 무조건 가상의 $n+1$번 정점으로 가고, $n+1$번 정점에서는 $n+1$번 정점으로만 갈 수 있도록 하면 된다.

Random Walk하면 Markov Chain이고 결국에는 행렬이다. 그러니 $p_k$는 선형점화식을 따른다. 

행렬의 크기가 $n$ 근처니 결국 점화식의 크기도 $n$ 근처다. 즉, 초기항 $2n$개 정도를 직접 $\mathcal{O}(nm) = \mathcal{O}(n^2)$ (planar graph에서 $|E| \le 3|V|-6$)에 구한 다음, Berlekamp-Massey를 돌려서 선형점화식을 구할 수 있다. 이제 우리의 목표는 $\sum_{k=0}^\infty kp_k$를 계산하는 것이다.

이는 생성함수를 이용하여 할 수 있다. $f(x) = \sum_{k=0}^\infty p_k x^k$라고 하자. 

$p_k$의 점화식을 알고 있기 때문에, 이를 활용하여 $f(x) = \frac{P(x)}{Q(x)}$가 성립하는 다항식 $P, Q$를 구할 수 있다.

목표는 $f'(1)$과 같고, $P, Q$를 계산하고 미분하는 것은 어렵지 않게 $\mathcal{O}(n^2)$에 할 수 있다.

이 문제도 이 글을 읽다가 키워드를 알게 되었다. 결론부터 말하면 답은 $p(n+1)-1$이고, Pentagonal Number Theorem으로 이를 계산할 수 있다. 

증명을 하기 위해서 perfect matching에 대한 자료를 찾아보다가, Tutte-Berge Formula를 찾았다.

이를 이용하여 증명을 할 수 있다. $G$가 조건을 만족하려면 $G$의 최대 매칭의 크기는 $n-1$이어야 한다.

그러니 $|U|-\operatorname{odd}(G-U)+2n = 2n-2$인 정점의 집합 $U \subset V$가 존재한다.

즉, $\operatorname{odd}(G-U) = |U|+2$인 $U$가 있다. $G$에 임의의 $G$에 없는 간선을 추가한 뒤에는 이 $U$에 대해서도 $\operatorname{odd}(G-U) = |U|$가 성립해야 한다. 

즉, $G$에 없는 간선은 전부 크기가 홀수인 컴포넌트 두 개를 잇는 간선이어야 한다. 이는 정말 강력한 조건이고, 여기서 정말 많은 정보를 얻어낼 수 있다.

우선 $G-U$의 각 컴포넌트는 전부 크기가 홀수여야 한다. 크기가 짝수인 컴포넌트가 있으면, "크기가 홀수인 컴포넌트 두 개를 잇는 간선"이 아니면서 $G$에 존재하지 않는 간선이 존재하게 되므로 모순이다. 비슷한 이유로, $G-U$의 각 컴포넌트는 전부 clique여야 한다. clique가 아니면, 컴포넌트 내부에서 그을 수 있는 간선이 있으므로 모순이다. 또한, 삭제한 정점의 집합 $U$에 속한 정점들은 차수가 $2n-1$이어야 한다. 차수가 $2n-1$이 아니면, 새로 그을 수 있는 간선이 존재하게 되기 때문이다. 이제 이를 종합하면, 원하는 그래프를 전부 classify 할 수 있다.

결론은 $G$가 차수 $2n-1$인 정점 $k$개와, 크기가 홀수이고 서로 "독립적인" clique $k+2$개로 분할된다는 것이다.

$k$를 고정하고 생각하면, 이때 $G$로 가능한 그래프의 개수는 홀수 $k+2$개의 합으로 $2n-k$를 만드는 경우의 수다.

이는 식을 잘 조작하면 $k+2$개의 자연수의 합으로 $n+1$을 만드는 경우의 수가 된다. 

이를 각 $k \ge 0$에 대하여 더하면, $p(n+1)-1$이 답임을 알 수 있고, 증명이 끝난다. 

문제 디스크립션이 무서워 보이지만, 결국에는 필요한 정보를 정말 다 준 디스크립션이다.

$\prod_{d|n} \Phi_d(x) = x^n-1$이고 $\Phi_d(x)$ 각각이 irreducible polynomial이므로, 문제는 결국 $\Phi_d$를 구하라는 것이다.

첫 아이디어로 가능한 것은 $\Phi_n(x) = \frac{x^n-1}{\prod_{d|n, d \neq n} \Phi_d(x)}$를 써서 계산하는 것인데, 이 방법은 간단하지 않은 다항식 나눗셈을 많이해야 하므로 비효율적이다.

여기서는 뫼비우스 반전을 생각할 수 있다. 결국 양변에 로그를 취한 다음 뫼비우스 반전을 적용하면, $\Phi_n(x) = \prod_{d|n} (x^d-1)^{\mu(n/d)}$를 얻는다. $x^d-1$ 형태의 다항식은 곱하기도 나누기도 간단하니, 계산을 효율적으로 할 수 있다. 특히, $\mu(n/d) \neq 0$인 경우에만 연산을 하면 되므로 연산 횟수도 생각보다 적다. 계산을 할 때, 먼저 곱할 다항식을 다 곱한 후 나눌 다항식을 나눠주는 게 좋다. 출력 형식을 맞춰주는 것은 적당히 정렬 하면 된다.   

문제를 적당히 해석한 뒤 Jimp Number가 정확히 어떤 자연수인지 classify 하는 것은 귀찮지만 어렵지는 않다.

결국 문제는 $n$ 이하 소수의 개수와, $n$ 이하 $4k+3$ 꼴 소수의 개수를 구하는 문제로 전환된다.

$n$ 이하 소수의 개수를 동적계획법으로 $\mathcal{O}(n^{3/4})$에 구하는 방법을 알고 있다면, 이를 간단하게 확장하여 $n$ 이하 $4k+3$ 꼴 소수의 개수를 구하는 $\mathcal{O}(n^{3/4})$ 알고리즘을 설계할 수 있다. 사실 앞에 $\phi(4)=2$라는 상수가 붙는다. 아무튼 이걸 짜면 아슬아슬하게 통과가 된다. 

결국 Project Euler 611의 하위호환. 이 문제가 classify 난이도 및 케이스 분석 면을 봤을 때 훨씬 더 어려운 문제 같다. 

사실 위에서 언급한 동적계획법은 top-down과 bottum-up 방식을 모두 활용한 뒤, offline query + fenwick tree를 이용하여 $\mathcal{O}(n^{2/3})$으로 최적화가 가능하다. 아니면 아예 Meissel-Lehmer Algorithm를 이용할 수도 있다. 확장이 잘 되는지는 모르겠다. 이런 방법들을 구현해야만 풀 수 있는 문제였다면 훨씬 더 어려운 문제가 되었을 것 같다. 정해는 offline query + fenwick tree로 최적화 하는 방법을 사용하는 것 같다. 이것도 한 번 짜보기는 해야될 듯.

다른 풀이로는 segmented sieve를 조져서 DB를 제작하는 풀이가 있었다고 한다. 엌ㅋㅋㅋㅋㅋㅋㅋㅋ

좋은 집합의 조건이 무엇인지를 먼저 판별해보자. 가장 typical한 것은 역시 \(0, a, 2a, 3a, \cdots \)다. 

좋은 집합 \(X\)를 생각하자. 일단 최대 원소 \(M\)을 잡으면, 문제 조건에서 \(2M\) 또는 \(0\)이 \(X\)에 속한다.

결론적으로 \(M=0\)이거나, \(0 \in X\)를 얻는다. 이건 어쨌든 \(0 \in X\)라는 뜻이다. 이제 \(X\)의 원소를 \(0, x_1, x_2, \cdots , x_n\)이라 하자. 

그러면 문제 조건에서 \(x_n-x_1, x_n-x_2, \cdots , x_n-x_{n-1}\)이 전부 \(X\)에 속해야 한다.

그런데 \(0<x_n-x_{n-1}<x_n-x_{n-2} < \cdots < x_n-x_1<x_n\)이니까, \(x_n=x_i+x_{n-i}\)가 전부 성립함을 알 수 있다.

비슷하게, \(x_{n-1}-x_2, x_{n-1}-x_3, \cdots , x_{n-1}-x_{n-2}\)를 생각할 수 있다. 

이를 반복하다 보면, 결국 \(x_i\)들이 앞에서 언급한 'typical한 경우'가 됨을 알 수 있다. 그런데 한 가지 예외 케이스가 발생한다.

\(X\)의 원소가 \(0, a, b, a+b\)인 경우가 조건을 만족함을 알 수 있다. 이 경우를 따로 처리해야 한다.

'typical한 경우'는 간단하게 \(\mathcal{O}(n \log n)\)에 계산할 수 있다. 예외 케이스는 FFT를 활용하여 어렵지 않게 \(\mathcal{O}(n \log n)\)에 계산할 수 있다. 

개인적으로는 재밌는 문제였다. 비슷한 문제를 수학 올림피아드에서 본 것 같은데 어디서 봤는지는 모르겠다.

일단 이 문제가 내가 최근에 Project Euler에서 푼 문제들보다는 좋은 것 같다. 재밌는 문제.

우리가 쉽게 계산할 수 있는 것에 어떤 것이 있는지를 먼저 생각해보자. 사전지식 점검이라고 볼 수 있다.

1. 주어진 선분 위에 (끝점 제외) 격자점이 몇 개 있는지를 셀 수 있고, 그 예시도 구할 수 있다. 이는 GCD만 알면 된다.

2. 삼각형의 넓이를 쉽게 구할 수 있고, 그 boundary 위에 놓인 격자점의 개수를 쉽게 셀 수 있다. 

3. 그러니, Pick's Theorem에 의하여, interior에 놓인 격자점의 개수를 쉽게 셀 수 있다. 즉, 답이 있는지 판별은 쉽다.

4. 물론, 특정 격자점이 삼각형 내부에 놓이는지 확인하는 것도 단순한 기하로 할 수 있다. 즉, 답이 맞는지 판별은 쉽다.

첫 번째 아이디어는, 삼각형을 더 작은 삼각형으로 쪼개는 것이다.

삼각형 \(\triangle ABC\)에서 \(BC\) 위에 (끝점 제외) 격자점 \(D\)가 있다고 하자.

그러면 선분 \(AD\) 위에 (끝점 제외) 격자점이 있는지 판별할 수 있고, 있다면 이를 답으로 찍으면 끝난다.

그렇지 않다면 \(\triangle ABD\) 내부 또는 \(\triangle ACD\) 내부에 격자점이 있어야 한다.

격자점 존재 여부는 판단하기 쉬우니, 격자점이 있는 쪽으로 탐색을 줄이면 될 것이다. 

\(D\)가 \(BC\)의 중점에 가깝도록 설정하면, 탐색하는 곳의 넓이가 대강 절반씩 줄어들 것이다.

이 과정을 당연히 각 변에 대해서 반복해가면, 답을 찾는데 성공하거나 \(AB, BC, CA\) 위에 (끝점 제외) 격자점이 없는 상태까지 줄일 수 있다. 

여기까지 로그 제곱의 기간이 걸린다. 이는 물론 각 단계에서 gcd를 계산해야 하기 때문이다.

답을 찾지 못했다면, \(AB, BC, CA\) 위에 (끝점 제외) 격자점이 없는 상태에 도달했다는 것이다.

일반성을 잃지 않고, \(AB\)가 가장 긴 변이라고 가정하자. 이제 핵심 결론을 제시한다.

직선 \(AB\)에 '가장 가까운 점' 중 하나가 무조건 삼각형 내부에 들어오게 된다. 

물론, 이 가까운 점이 \(AB\) 기준 위에 있는지 아래에 있는지를 확인하려면 CCW 등의 계산을 해야 한다.

\(AB\)에 가장 가까운 점을 계산하는 것은 어렵지 않게 extended euclidean algorithm으로 할 수 있다.

이제 답을 찾는 것도 크게 어렵지 않다. 적당히 '가장 가까운 점'을 보면서 답이 맞는지 판별하면 되기 때문이다.

가장 가까운 점이 삼각형 내부에 들어오게 된다는 것은, Stern-Brocot Tree를 생각하면 어렵지 않다.

대충 생각하면, 가장 가까운 점이 삼각형 내부에 들어오지 못하도록 \(C'\)을 잡으려면 \(AC'\) 또는 \(C'B\)의 기울기가 굉장히 작은 interval 안에 들어가야 하고, Stern-Brocot Tree의 원리에서 그 interval 안에 들어가려면 \(AC'\) 또는 \(C'B\)의 길이가 \(AB\)보다 커진다는 것을 증명할 수 있다. 디테일은 생략.

지금 생각하는 건데, '가장 가까운 점'에 대한 추측을 하면 이분탐색 + 변 기준 CCW로도 해결할 수 있을 것 같다. 

그런데 이걸 쉽게 하려면 (아마) __int128이 필요할 것이다. Atcoder에서 __int128을 지원하는지는 모르겠다.

LIS가 2 이하라는 것은, 123-avoiding permutation이라는 것이다. 편의상 \(1\)-index로 문제를 풀자.

123-avoiding permutation 문제에서 경우의 수를 세라는 것은, 대충 카탈란 수에 대한 사전지식을 필요로 한다는 것이다.

123-avoiding permutation과 dyck path (즉, \((0,0)\)에서 \((n,n)\)까지 \(y=x\)를 뚫지 않고 가는 경로) 사이의 대응을 알아야 한다.

123-avoiding permutation \(p_1, p_2, \cdots , p_n\)이 있다고 하자. 이를 오른쪽에서 왼쪽으로 차례대로 볼 준비를 하자.

오른쪽에서 왼쪽으로 가면서, 지금까지 본 "역대 최대"를 기록하자.

"역대 최대"의 index가 순서대로 \(n=x_1 > x_2 > \cdots > x_k\)라고 하고, 그때의 값을 \(y_1 < y_2 < \cdots < y_k = n\)이라고 하자.

핵심 관찰은, "역대 최대" 사이의 "블록"들은 무조건 감소한다는 사실이다.

이게 뭔 뜻이냐면, 주어진 permutation이 \([x_2+1, x_1-1]\), \([x_3+1, x_2-1]\) 등에서 감소한다는 것이다.

만약 \(i, j \in [x_2+1, x_1-1]\)가 있어 \(i<j\)고 \(p_i < p_j\)라면, \(p_i < p_j < p_{x_1}\)이므로 123-avoiding에 모순이다.

또한, 예를 들어 \(i \in [x_3+1, x_2-1]\), \(j \in [x_2+1, x_1-1]\)이고 \(p_i < p_j\)라면, 마찬가지 이유로 123-avoiding에 모순이다.

즉, "역대 최대"로 찍힌 친구들을 제외하면 전부 다 감소한다. 이건 굉장히 중요한 사실이다.

이제 123-avoiding permutation과 dyck path 사이의 일대일대응을 설계할 준비가 끝났다.

\((0,0)\)에서 시작해서, \((y_1, 0)\)까지 가자. 그런 다음, \((y_1, n-x_2)\)까지 쭉 올라가자.

그 다음, \((y_2, n-x_2)\)까지 간 다음 \((y_2, n-x_3)\)까지 쭉 올라가자. 이를 반복해서 \((n,n)\)까지 가자.

이게 dyck path임을 증명하는 것은 어렵지 않다. 또한, 이게 일대일대응임을 증명하는 것도 어렵지 않다.

\(x_1, x_2, x_3, \cdots, x_k , y_1, y_2, \cdots , y_k\)를 결정하면 123-avoiding permutation 자체가 결정되기 때문이다.

추가: 위 논의를 정리하면 결국 123-avoiding permutation이 2개의 감소 수열로 분할된다는 것이다.

이건 사실 Dilworth's Theorem의 입장에서 보면 매우 당연한 사실이다. 이 글의 G번을 참조하자. 

이제 본격적으로 주어진 문제를 풀어보자. \(a, b\)를 전부 \(1\)-index로 바꾸자.

만약 \(a+b < n+1\)이라면, \(a\)를 \(n+1-a\), \(b\)를 \(n+1-b\)로 바꿔주자. 

이것이 가능한 이유는, \(p_1, p_2, \cdots , p_n\)을 \(n+1-p_n, n+1-p_{n-1}, \cdots , n+1-p_1\)으로 뒤집을 수 있기 때문이다.

그런데 \(a+b \ge n+1\)이면, \(p_a=b\)는 "역대 최대"일 수 밖에 없다.

"역대 최대"가 아니라면, \(1, 2, \cdots , b-1\) 전부와 \(b\)보다 큰 값 적어도 하나가 \(p_{a+1}, p_{a+2}, \cdots p_n\)에 들어있어야 한다.

이는 \(n-(a+1)+1 = n-a \le b-1\)이므로 모순이다. 

즉, dyck path의 입장으로 보면 우리의 dyck path는 \((b-1, n-a)\)에서 \((b, n-a)\)로 이동한 뒤, \((b, n-a+1)\)로 올라가는 경로다. 

이 path는 크게 세 단계로 쪼개서 볼 수 있다. 

단계 1에서는 \(y=x\) 위를 뚫지 않고 \((0,0) \rightarrow (b-1, n-a)\)을 한다.

단계 2에서는 \((b-1, n-a) \rightarrow (b, n-a) \rightarrow (b, n-a+1)\)을 한다.

단계 3에서는 \(y=x\) 위를 뚫지 않고 \((b, n-a+1) \rightarrow (n, n)\)을 한다.

이 세 단계는 각각 독립적이다. 그러니, 단계 1, 단계 3으로 고를 수 있는 path의 개수를 세면 된다.

또한, 단계 3의 path는 \(y=x\) 위를 뚫지 않고 \((0,0) \rightarrow (a-1, n-b)\)를 하는 path와 쉽게 대응이 된다.  

즉, \(y=x\) 위를 뚫지 않고 \((X, Y)\)로 가는 (단, \(X \ge Y\)) path의 개수를 셀 줄 알면 된다.

이는 매우 유명한 "대칭" 테크닉으로 쉽게 계산할 수 있다. \(y=x\) 위를 뚫는 path는 \(y=x+1\) 위의 점을 지난다.

path와 \(y=x+1\)의 첫 번째 교점을 잡고, 그 이후의 path를 \(y=x+1\)을 기준으로 대칭하자.

그러면 이는 \((Y-1, X+1)\)으로 가는 경로와 일대일대응됨을 알 수 있다. 즉 답은 \(\binom{X+Y}{X} - \binom{X+Y}{X+1}\)이다.

여담: 계산해야 하는 factorial의 개수가 \(\mathcal{O}(1)\)이라, 이 문제를 쓰면 더 빠르게 풀 수 있다. ㅋㅋ!

이 글에 나온 이 문제의 풀이를 참고하라. 분할 정복 등의 풀이가 있는 것으로 알지만, 필요 없다.

전체의 각 부분집합 \(X\)에 대하여, \(a(X)\)를 [\(X\)의 원소를 하나도 포함하지 않도록 박스를 고르는 경우의 수]라고 하자.

그러면 포함배제의 원리를 이용하여 답을 \(a(X)\)에 대한 식으로 간단하게 쓸 수 있다.

한편, \(b(X)\)를 [\(X\)의 원소를 하나도 포함하지 않는 박스의 수]라고 하면 \(a(X)=2^{b(X)}\)가 성립한다.

이제 목표는 \(b(X)\)의 값을 전부 구하는 것이고, 이는 SOS DP를 이용하면 쉽게 계산할 수 있다.

이런 카운팅 문제는 보통 (원순열처럼) 가능한 경우의 수를 naive하게 센 다음 중복을 제거하는 방식으로 해결한다.

naive하게 세는 방법은 \([1,k]\) 부분과 \([k+1,n]\) 부분이 각각 palindrome이 되는 문자열의 개수를 전부 더하는 방법이다.

중복이 되는 경우는 어떤 경우일까? 두 정수 \(p, q\)가 존재하여, \([1,p],[1,q],[p+1,n],[q+1,n]\)이 모두 palindrome이 되는 문자열은, 중복되어 세질 것이다. 이런 문자열들은 주기가 있는 문자열이라는 것을 어렵지 않게 파악할 수 있다.

이를 기반으로, 중복되어 세질 문자열 \(S\)를 잡고 \(S=RRR\cdots R\) 형태로 써보자. 단, \(R\)을 minimal하게 잡자.

그러면 \(R\)이 어떠한 형태를 가져야 하는지 알 수 있고, 이때 \(S\)가 얼마나 중복되어 세지는 지 파악할 수 있다.

이 과정을 모두 마쳤다면, 답에 대한 일종의 점화식을 설계할 수 있을 것이다. 코드는 매우 간단하다.

\(k=2\)인 경우를 먼저 설명한다. 모든 연산을 \(\pmod{2}\)로 하자. 문제에서 주어진 벡터들을 행으로 갖는 행렬 \(A\)를 생각하자.

조건을 만족하는 \(p, q\)가 아예 없다면, \(AA^T\)는 대각성분을 제외하고 전부 \(1\)일 것이다.

또한, \(AA^T\)의 실제 대각성분은 쉽게 계산할 수 있다. 즉, 조건을 만족하는 \(p, q\)가 존재하는지 여부를 판별하는 것은 다음 문제와 같다.

문제: 이미 모든 entry를 알고 있는 행렬 \(C\)가 있다. \(AA^T = C\)인가?

이 문제는 단순히 \(AA^T\)를 계산하는 방법보다 더 빠른 방법이 있다. Freivald's Algorithm을 참고하라. 

이제 조건을 만족하는 \(p, q\)가 존재하는지 판별할 수 있고, 이를 확장하면 존재하는 경우 \(p, q\)의 예시도 구할 수 있다.

여기까지 잘 이해했다면, \(k=3\)인 경우에는 상황이 간단하지 않다는 것을 쉽게 파악할 수 있을 것이다. 

\(a \not\equiv 0 \pmod{3}\)이면 \(a^2 \equiv 1 \pmod{3}\)임을 활용해보자. 이 아이디어는 나도 생각 못했다 :(

핵심 관찰은 \(d_i(a) = \sum_{j} [\text{min}_{k \in [i, j]} a_k = a_j]\)가 성립한다는 것이다.

\(i>j\)인 경우 구간은 \([j, i]\)로 바뀌며, \([P]\)는 \(P\)가 참이면 1, 거짓이면 0이다.

이제 문제는 \(a_j = \text{min}_{k \in [i, j]} a_k\)이며 inversion의 개수가 \(K\)인 permutation의 개수를 세는 것이다.

이 문제를 해결하려면, inversion의 개수에 대한 generating function과 그 유도를 알고 있어야 한다.

generating function이 무엇인지는 Wikipedia 자료를 참고하라.

이런 전형적인 순열에 대한 문제를 풀어봤다면, 다음을 쉽게 증명할 수 있을 것이다.

\(inv_i\)를 \(i<j\)이고 \(a_i > a_j\)인 \(j\)의 개수라고 하자. 자명하게 \(0 \le inv_i \le n-i\)다.

이제 저 조건을 만족시키면서 \(inv_1, inv_2, \cdots , inv_n\)을 고정하면, 이에 대응되는 permutation이 유일하게 존재한다.

여기서 우리는 inversion의 개수에 대한 generating function이 \(\prod_{i=0}^{n-1} (1+x^1+ \cdots + x^i)\)임을 알 수 있다.

이 아이디어를 확장하면, 위 문제도 해결할 수 있을 것이다. 무엇을 어떻게 고정할지 고민해보자.

그림을 대칭시켜서 보는 아이디어는 굉장히 유명하다. 그러면 모든 것을 \(\pmod{2w}\), \(\pmod{2h}\)로 볼 수 있다.

이제 다각형의 한 변과 공이 부딪힐 조건을 생각해보면, \(L \le ax \pmod{m} \le R\) 형태의 식을 얻을 수 있다.

\(a, m, L, R\)이 주어졌을 때 \(L \le ax \pmod{m} \le R\)의 최소해 \(x\)를 구해야 하는데, 여러 방법이 있다.

방법 1: 전형적인 "유클리드 알고리즘처럼 문제 환원하기" - 이 문제와 이 글 참고

\(a, m, L, R\)에 대한 문제를 작은 문제로 환원할 수 있다. \(a-m \pmod{a}, a, L \pmod{a}, R \pmod{a}\)에 대한 문제로 환원해보자.

방법 2: Binary Search + Lattice Point Counting Algorithm (koosaga님에게 들은 풀이)

주어진 문제를 \(ax+my \le mT+L-1\)인 Lattice Point의 개수와 \(ax+my \le mT+R\)인 Lattice Point의 개수가 달라지는 최소의 \(T\)를 계산하는 문제로 바꿀 수 있다. 이는 Binary Search가 가능한 형태임을 알 수 있고, 남은 것은 삼각형 형태의 영역에서 Lattice Point의 개수를 세는 것이다.

물론, 여기서 Lattice Point는 \(x, y \ge 0\)이고 \(x, y\)가 모두 정수인 \((x,y)\)를 말한다.

이 문제는 다시 "유클리드 알고리즘처럼 문제 환원하기" 테크닉을 사용하여 해결할 수 있는 문제다. 직접 해보자. 

나머지는 그냥 깡구현이다. 여러모로 많은 것을 배울 수 있던 문제였다. Project Euler 700번도 이 방식으로 풀 수 있다.

핵심 관찰은 특정 pillar가 보인다면, pillar의 중심도 무조건 보인다는 것이다. 직관적으로 자명하고, 증명도 어렵지 않다.

이제 특정 점이 보일 조건을 수식으로 쓰자. 점에서 직선 사이의 거리 등을 활용하면 간단하다.

결론적으로 이 문제는 \(x^2+y^2 \le r^2\) 형태의 원 내부에서 \(\text{gcd}(x,y)=1\)인 정수점의 개수를 세는 문제로 환원이 된다. 

이 문제는 이 글에 나와있는 요 문제와 비슷한 느낌을 갖는다. 하지만 제한이 조금 더 빡세졌다. 

하지만, 뫼비우스 반전을 이용하면 이 문제 역시 크게 어렵지 않게 해결할 수 있다. 좋은 문제인지는 잘 모르겠다.

당연히 Burnside's Lemma를 이용하는 문제고, 이 문제는 이 문제집을 본 이후로 내게 숙제로 남아있었다.

Burnside's Lemma를 완전하게 (즉, Group Action에 대한 정리로) 이해해야 해결할 수 있는 문제인만큼, 난이도가 상당하다.

우선 문제를 Burnside's Lemma의 언어로 번역하기 위해, 정확하게 어떤 Group이 Act하고 있는지를 생각해보자.

당연히 돌려서 같은 경우/뒤집어서 같은 경우가 같은 것으로 취급되니, Dihedral Group \(D_n\)이 등장한다.

이제 색을 서로 교환해서도 같은 경우로 취급되는데, 이것은 Symmetric Group \(S_k\)로 생각할 수 있을 것이다.

조금 더 생각을 해보면, 우리는 direct product \(D_n \times S_k\)를 우리의 Group으로 설정할 수 있을 것이다.

이제 Burnside's Lemma의 흐름을 따라가면, 각 \((g, \sigma) \in D_n \times S_k\)에 대해서 left invariant의 개수를 세면 된다.

\(D_n\)의 각 원소 \(g\)가 만드는 cycle 구조와, \(S_k\)의 각 원소 \(\sigma\)의 cycle 구조를 생각해보자.

이를 잘 생각해보면, (특히, 이 문제보다 쉬운 Burnside's Lemma 활용 문제를 많이 풀어봤다면) 답을 어렵지 않게 구할 수 있을 것이다. 

계산을 하다가 막힌다면, \(D_n\)과 \(S_k\)의 Cycle Index를 참고하는 것을 추천한다.

더 어려운 Burnside's Lemma 활용 문제를 풀고 싶다면, Project Euler 626, 651을 풀자.

UPD 1: 651번은 풀었다. 사전지식이 하나 더 았어야 651번을 풀 수 있다. 그래도 이 문제가 더 어려운듯?

UPD 2: 626번도 풀었다. Group 잘 설정한 뒤에도 여러 난관이 있는 아주 재밌는 문제다. 626, 651 모두 추천한다.

결국에는 "경로에 대하여 어떤 함수를 적분한 것"을 최소화하는 경로를 찾는 문제다.

수학 책을 좀 읽었거나 (서울대 기준) 미적분학 2+ 책을 열심히 읽었다면, 변분법을 생각할 수 있을 것이다.

변분법을 생각하면, \(x, f(x), f'(x)\)를 알 때 \(f''(x)\)를 계산할 수 있을 것이다. 계산은 알아서 열심히 하자.

초기 \(x, f(x)\)의 값과 최종 \(x, f(x)\)의 값을 알고 있으니, 초기 \(f'(x)\) 값을 정하고 적당히 이분탐색을 하면 될 것이다.

선형대수학, 현대대수학과 일부 알고리즘 지식을 총동원해서 풀어야 하는 문제다. 

풀이를 설명하는 대신, 필요한 사전지식을 전부 나열한다. 이를 공부하고 합치는 것은 문제를 푸는 사람의 몫인 것 같다.

• Annihilator와 Minimal Polynomial
• Minimal Polynomial을 어떻게 계산할 것인가 (내가 지금까지 본 방법은 두 가지가 있다)
• 어디서나 쓰이는 "학부 대수학의 반" - \(\mathbb{Z}\)의 subgroup은 \(n\mathbb{Z}\) 형태 뿐이다.
• 학부 대수학의 반은 직접 사용되지는 않으나, 풀이를 설계하고 이해하는데 도움이 된다.
• Frobenius Endomorphism
• Lemma: \(x^{q^n}-x\)은 degree가 \(n\)의 약수인 모든 monic irreducible polynomial in \(\mathbb{F}_q\)의 곱이다.
• 개인적으로는 bitset을 오랜만에 사용해서, 이것도 공부해서 풀었다.

\(T_n\)이 카탈란 수인 것은 유명하다. 이제 얘를 \(\pmod{m}\)으로 계산해야 한다.

\(m\)이 소수라면 팩토리얼 값을 전부 전처리한 다음에 계산하면 끝이지만, \(m\)이 합성수라서 문제가 꽤 매워진다.

\(C_{n+1} = \frac{2(2n+1)}{n+2} C_n\)이므로, 카탈란 수를 소인수분해된 형태로 저장할 수 있다.

그러니 각 소수를 leaf로 하는 곱셈 세그먼트 트리를 구성하면, 나눗셈 걱정 없이 문제를 해결할 수 있다.

\(\frac{2(2n+1)}{n+2}\)를 소인수분해한 다음, 이에 맞게 세그먼트 트리를 업데이트하면 된다.

Linearity of Expectation을 활용하는 문제다. 우선 \(E(S) = E(\sum_{v=1}^5 vc^2_v) = \sum_{v=1}^5 v E(c^2_v)\)다.

이제 \(E(c^2_v)\)를 구하는 방법을 생각해보자. \(S_{i,j}\)를 \([1,i] \times [1,j]\)에 존재하는 \(v\)의 개수라고 하자. 

\([i, k] \times [j, l]\) 사각형을 선택한다면, 이때 \(c^2_v\)의 값은 \((S_{k,l}-S_{i-1,l}-S_{k,j-1}+S_{i-1,j-1})^2\)이다. 

이를 전개하면 복잡한 식이 나오는데, 각각의 기댓값을 직접 계산할 수 있다. 꽤 고통스럽다.

\(S_{i,j}\)의 2차원 부분합을 계산하고, \(\sum_{i<j} 2x_i x_j = (\sum_{i} x_i)^2 - \sum_{i} x^2_i\) 등을 활용하면 된다.

\(D = p^{e_1}_1 p^{e_2}_2 \cdots p^{e_k}_k\)라 하자. 또한, \(\binom{m}{n} = p^{f_1}_1 p^{f_2}_2 \cdots p^{f_k}_k \cdot X\)라 하자.

우선 \(e_i\)들과 \(p_i\)들은 \(D\)를 소인수분해하여 쉽게 얻을 수 있다. 

그러니 \(f_i\)들도 \(v_p(n!) = \frac{n-s_p(n)}{n-1}\)이라는 공식을 이용하면 쉽게 얻을 수 있다.

여기서 \(D^t|\binom{m}{n}\)인 최대의 \(t\)도 얻을 수 있다. 이제 \(X \pmod{D}\)만 계산하면 답을 쉽게 얻을 수 있다.

\(X \pmod{p^{e_i}_i}\)를 각 \(i\)에 대해서 구한 다음, 중국인의 나머지 정리로 합치자.

\(m! = p^k \cdot Y\)라 할 때, (단, \(\text{gcd}(p,Y)=1\)) \(Y \pmod{p^e}\)를 \(f(m,p,e)\)라 하자. 

그러면 \(f(m,p,e) \equiv f(p^e-1, p, e)^{\lfloor \frac{m}{p^e} \rfloor} \cdot f(m \pmod{p^e}, p, e) \cdot f(\lfloor \frac{m}{p^e} \rfloor , p, e) \pmod{p^e}\)가 성립한다. 

각 \(0 \le i < p^e\)에 대하여 \(f(i,p,e)\)를 전처리하면, \(f(m,p,e)\)를 로그 시간에 계산할 수 있다.

한편, \(f(m,p,e)\)는 \(p\)와 서로소이므로, \(\pmod{p^e}\)에 대한 modular inverse를 생각할 수 있다.

이제 \(f(m,p,e)\)의 정의에서 \(\frac{f(m,p_i,e_i)}{f(n,p_i,e_i) \cdot f(m-n, p_i, e_i)} \equiv \prod_{j \neq i} p^{f_j}_j \cdot X \pmod{p^{e_i}_i}\)임을 알 수 있다.

이 식에서 modular inverse 등을 적당히 계산하면 \(X \pmod{p^{e_i}_i}\)를 계산할 수 있다.

아이디어는 전형적인데, 디테일을 생각하는 것은 조금 어려웠다. 재밌는 문제.

\(n\)개의 매칭이 있는 그래프를 \(2n\), \(2n+1\)개의 매칭이 있는 그래프로 바꿔보자.

\(n\)에서 \(2n\)으로 가는 것은 길이 4인 사이클을 추가해주면 간단하다. 

\(n\)에서 \(2n+1\)로 가는 것은 약간 애매하다. 정확히 하나의 매칭을 더 만들어야 한다. 

한 간선이 정해지면 다른 간선이 전부 강제로 정해져서 딱 하나의 매칭이 만들어지는 큰 그림을 그려보자.

작은 \(n\)에 대해서 적당히 실험을 해보면 방법을 찾을 수 있다. 

길이 4인 사이클을 추가할 때, 기존에 있던 그래프와 연결되도록 절선 간선을 적당히 하나 붙이자.

절선 간선이 추가되어도, 매칭의 개수는 변화하지 않음을 쉽게 알 수 있다.

이제 \(n\)에서 \(2n+1\)로 가보자. 먼저 앞선 방법처럼 길이 4인 사이클을 추가한 뒤 절선 간선을 적당히 하나 붙이자.

여기서 1번 정점에서 새로 추가한 정점으로 가는 간선을 하나 넣으면, 정확히 하나의 매칭이 추가됨을 알 수 있다.

각 화물열차를 하나의 다항식으로 보면, 목표는 두 다항식을 곱했을 때 계수가 가장 큰 차수를 찾는 것이다.

\([a,b]\)에 컨테이너가 놓여있으면, 대응되는 다항식은 \(t^a+ \cdots + t^b = \frac{t^a-t^{b+1}}{1-t}\)다.

그러니 두 다항식의 곱은 \(\frac{1}{(1-t)^2} \cdot (\sum_{i=1}^n t^{X_i} - t^{Y_i+1}) \cdot (\sum_{i=1}^m t^{Z_i} - t^{W_i+1})\)이다.

편의상 \((\sum_{i=1}^n t^{X_i} - t^{Y_i+1}) \cdot (\sum_{i=1}^m t^{Z_i} - t^{W_i+1}) = \sum_i c_i t^{d_i}\)라 하자. 단, \(c_i \neq 0\)이다.

한편, \(\frac{1}{(1-t)^2} = \sum_{i=0}^\infty (i+1)t^i\)이므로, \(t^k\)의 계수는 \(\sum_{d_i \le k} c_i(k-d_i+1)\)이다.

이는 \(k\)에 대한 일차식이고, 그 일차식의 \(k\)에 대한 계수 \(\sum_{d_i \le k} c_i\)는 \(k=d_i\)에서 변화한다.

그러니 최댓값을 구하려면 \(k=d_i-1,d_i\)인 경우에만 \(t^k\)의 계수를 구하면 충분하다.

모든 계산은 lower_bound와 부분합 등을 적당히 활용하여 빠르게 할 수 있다. 메모리 제한에 주의하자.

\(V(G) = [n] = \{1, 2, \cdots , n\}\)이라는 notation을 활용한다. 편의상 empty set은 independent set이 아니라고 하자.

주어진 그래프 \(G\)의 간선에 방향을 적당히 줘서, 사이클이 없도록 만들어주면 된다. 

DAG에서 각 간선의 방향을 전부 뒤집어도 DAG이므로, 답은 방향을 주는 방법의 수에 \(\frac{m}{2}\)를 곱한 값이다.

그런데 그래프의 acyclic orientation의 개수는 \(\chi_G(-1) \cdot (-1)^{|V(G)|}\)임이 알려져 있다. 

여기서 \(\chi_G(k)\)는 \(G\)의 chromatic polynomial이다. 

각 \(S_i\)가 \(G\)의 independent set이고, \(\sum_{i=1}^r |S_i| = n\), \(\cup_{i=1}^r S_i = [n]\)인 \(r\)-tuple \((S_1, S_2, \cdots , S_r)\)의 개수를 \(p(r)\)이라 하자. independent set으로 그래프를 분할한 것이다. 그러면 \(\chi_G(k) = \sum_{r=1}^n \binom{k}{r} p(r)\)가 성립한다.

그러니 여기에 \(k=-1\)을 대입하여 \(\chi_G(-1) = \sum_{r=1}^n (-1)^r p(r)\)임을 알 수 있다.

각 \(X \subseteq [n]\)에 대하여, 각 \(S_i\)가 \(G\)의 independent set이고 \(\sum_{i=1}^r |S_i| = n\)이며 각 \(i\)에 대해 \(S_i \cap X = \emptyset\)인 \(r\)-tuple \((S_1, S_2, \cdots , S_r)\)의 개수를 \(a_r(X)\)라고 정의하자. 포함-배제의 원리를 생각하면, \(p(r) = \sum_{X \subset [n]} (-1)^{|X|} a_r(X)\)가 성립한다. 정리하면 \(\chi_G(-1) = \sum_{X \subseteq [n]} \sum_{r=1}^n (-1)^{r+|X|} a_r(X)\)를 얻는다.

이제 \(X\)를 고정하고 생각하자. \(dp[i][j]\)를 [크기의 합이 \(j\)]인 [\(i\)개의 independent set]을 선택하는 방법의 수라고 하자. 

선택 순서는 중요하고, 각 independent set은 \([n] \setminus X\)에 속해야 한다. 크기가 \(k\)이고 \(X\)에 속하는 independent set의 개수를 \(S(X, k)\)라 하면 \(dp[i][j] = \sum_{k=1}^j dp[i-1][j-k] \cdot S([n] \setminus X, k)\)가 된다. 물론 \(a_r(X) = dp[r][n]\).

\(S(X, k)\)의 값들을 이미 계산했다고 생각하면, DP 테이블을 채우는데 \(\mathcal{O}(n^3)\)의 시간이 필요하다. 이를 각 \(X\)에 대해서 계산하려면 \(\mathcal{O}(n^3 2^n)\)의 시간이 필요해 TLE를 받는다. 하지만 우리가 계산해야 하는 값은 \(\sum_{r=1}^n (-1)^r a_r(X)\)이니, \(r\)의 홀짝성만 알면 된다. 그러니 DP 테이블의 정의를 변형할 수 있다. independent set의 개수 대신, 개수의 홀짝성만을 생각하면 된다. 이를 이용하면 DP 테이블을 \(\mathcal{O}(n^2)\)에 계산할 수 있고, 전체적으로 \(\mathcal{O}(n^2 2^n)\)의 시간에 계산을 마칠 수 있다. 

이제 남은 것은 \(S(X, k)\)의 값을 빠르게 계산하는 것이다. 먼저 각 \(2^n\)개의 부분집합이 independent set인지 여부를 미리 전처리하자. 이제 \(|X|=k\)이고 \(X\)가 independent set이면 \(F(X, k)=1\)이라고 두고, 그렇지 않으면 \(F(X, k)=0\)이라 하자. 여기까지는 \(\mathcal{O}(n2^n)\)에도 할 수 있다. 한편, \(S(X,k) = \sum_{Y \subseteq X} F(Y, k)\)가 된다. 이는 Sum over Subsets DP 테크닉을 이용하면 \(\mathcal{O}(n^22^n)\)에 계산할 수 있다. 이렇게 하면 모든 과정을 \(\mathcal{O}(n^2 2^n)\)에 할 수 있다. 끝.

굉장히 어려운 방법이지만, 이 풀이에서 배울 수 있는 점은 많다고 생각한다. 포함-배제 관련 테크닉은 다 할 수 있을 듯.

특히, 다른 사람들이 분할-정복 등의 복잡한 방법을 선택한 문제인 이 문제도 굉장히 쉽게 해결할 수 있다.

\( W = \{0, 1, \cdots , 9\}\)라고 하자. 마나 \(i\)의 양을 \(x_i\)라 하자. 

또한, \(i\)번째 경우에서 \(j\)번째 마나가 증가하는 양을 \(f_{i,j}\)라 하자.

\(T\)번의 수련 이후에 어떤 확률변수 \(X\)의 기댓값을 \(E(X, T)\)라 하자. 

각 \(S \subseteq W\)에 대하여 확률변수 \(\prod_{i \in S} x_i\)를 \(m_S\)라 하자.

특히, 특별히 (abuse of notation) \(E(S, T) = E(m_S, T)\)라고 정의하자. 

또한, \(A^T \cdot E(X, T) = P(X, T)\)라 하고, 마찬가지로 \(P(S, T) = P(m_S, T)\)라 하자. 

즉, \(P(X, T)\)는 가능한 모든 경우에 대한 \(X\)의 합이다. 이제 문제를 풀어보자.

\(\displaystyle E(S, T) = \frac{A - \sum_{i=1}^N P_i}{A} E(S, T-1) + \sum_{i=1}^N \frac{P_i}{A} \cdot E(\prod_{j \in S} (x_j+f_{i,j}), T-1) \)이 성립함을 알 수 있다.

이를 정리하면, \(\displaystyle E(S, T) = E(S, T-1) + \sum_{S' \subsetneq S} \text{coef}_{S', S} \cdot E(S', T-1) \) 형태의 식을 얻는다.

그런데 식을 자세히 보면, \(\displaystyle \text{coef}_{S', S} = \sum_{i=1}^N \frac{P_i}{A} \cdot \prod_{j \in S \setminus S'} f_{i,j}\)가 된다. 즉, \(\text{coef}_{S', S}\)는 사실 \(S \setminus S'\)에 의해서만 결정된다.

\(\displaystyle \text{coef}_{S', S} = \frac{1}{A} \cdot c_{S \setminus S'}\)으로 두면 \(\displaystyle E(S, T) = E(S, T-1) + \sum_{S' \subsetneq S} \frac{1}{A} \cdot c_{S \setminus S'} \cdot E(S', T-1)\)을 얻는다.

이제 \(A^T\)를 곱하면, \(\displaystyle P(S, T) = A \cdot P(S, T-1) + \sum_{S' \subsetneq S} c_{S \setminus S'} \cdot P(S', T-1)\)을 얻는다.

물론, \(c\)에 해당하는 값들을 계산하는 것은 \(\mathcal{O}(2^{10} \cdot N)\)에 할 수 있다.

이를 빠르게 계산하기 위해서, directed weighted graph \(G\)를 하나 구축하자. 

\(G\)의 정점은 \(W\)의 부분집합들이다. 각 점에는 weight \(A\)를 갖는 self-loop가 하나 있다.

또한, \(S' \subsetneq S\)이면 \(S'\)에서 \(S\)로 가는 가중치 \(c_{S \setminus S'}\)의 간선을 긋자.

또한, path \(P\)의 가중치를 \(P\)가 지나간 간선들의 가중치의 곱으로 (중복 포함) 정의하자.

이제 각 \(S \subseteq W\)에 대해서 \(P(S, 0)=1\)임을 생각하자. 그러면 \(P(S, T)\)는 [\(S\)에서 끝나고 \(T\)개의 간선으로 이루어진 모든 path]의 가중치를 더한 값임을 알 수 있다. 한편, 각 경로에서 self-loop가 아닌 간선은 최대 \(10\)개 뿐이다. 또한, 모든 self-loop의 가중치는 \(A\)로 동일하다. \(dp[S][i]\)를 [\(S\)에서 끝나고 \(i\)개의 [self-loop가 아닌 간선]만으로 이루어진 모든 path]의 가중치를 더한 값이라고 정의하자. 그러면 \(\displaystyle dp[S][i] = \sum_{S' \subsetneq S} dp[S'][i-1] \cdot c_{S \setminus S'}\)가 된다. DP 테이블을 채우는 것은 \(\mathcal{O}(10 \cdot 3^{10})\) 시간에 할 수 있다. 그러면 \(\displaystyle P(S, T) = \sum_{i=0}^{\text{min}(10, T)} dp[S][i] \cdot A^{T-i} \cdot \binom{T}{i} \)가 된다. \(A^{T-i}\)는 경로에서 \(T-i\)번 self-loop를 이용한 것에서 나오고, \(\binom{T}{i}\)는 \(T\)번의 간선 이동 중 언제 self-loop를 이용할 지를 결정하는 과정에서 나온다. 이항 계수는 \(i\)가 작으니 직접 계산하면 된다. 답은 \(P(W, T)\)다. 끝.

먼저 필요한 제곱수의 개수를 판별하는 방법부터 알아보자. 

임의의 자연수는 4개의 제곱수의 합으로 표현할 수 있다. (라그랑주의 네 제곱수 정리)

\(4^a(8b+7)\) 형태의 자연수가 아니면, 3개의 제곱수의 합으로 표현할 수 있다. (르장드르의 세 제곱수 정리)

임의의 \(4k+3\)꼴 소수 \(p\)에 대하여 \(v_p(n)\)이 짝수면, 2개의 제곱수의 합으로 표현할 수 있다. (페르마의 두 제곱수 정리 활용)

마지막으로, 당연히 제곱수는 1개의 제곱수의 합으로 표현할 수 있다. 

그러니 필요한 제곱수의 개수는 pollard-rho 소인수분해를 이용하면 쉽게 판별할 수 있다. 여기까지가 이 문제.

이제 제곱수의 합으로 표현하는 방법을 생각해보자. 제곱수 1개가 필요한 경우에는 딱히 설명할 필요도 없다.

\(N\)을 표현하기 위해 제곱수 4개가 필요한 경우를 먼저 보자. \(N=4^a(8b+7)\)이라고 하자.

\(8b+6\)은 제곱수 3개로 표현할 수 있으므로, 그 방법을 찾아서 \(8b+6=x^2+y^2+z^2\)이라 하자.

그러면 \(N = (x \cdot 2^a)^2 + (y \cdot 2^a)^2 + (z \cdot 2^a)^2 + (2^a)^2\)이 된다. 끝.

\(N\)을 표현하기 위해 제곱수 3개가 필요한 경우를 보자.

\(x\) 이하의 자연수 중 두 제곱수의 합으로 표현될 수 있는 수의 개수는 대략 \(\displaystyle K \cdot \frac{x}{\sqrt{\ln x}}\)임이 알려져 있다.

여기서 \(K\)는 Landau-Ramanujan 상수다. 즉, 임의의 \(t\)를 하나 잡으면, \(N-t^2\)이 두 제곱수의 합으로 표현될 확률이 그렇게 나쁘지는 않다는 것이다. 그러니 \(t\)를 \(1\)부터 점점 증가시키면서, \(N-t^2\)을 두 제곱수의 합으로 표현하려고 시도하는 것을 반복하자. 성공하면 \(N-t^2=x^2+y^2\)을 얻고, 이는 결국 \(N=x^2+y^2+t^2\)이 된다. 끝. 

이제 \(N\)을 표현하기 위해 제곱수 2개가 필요한 경우를 보자.

\(N = T^2 \cdot p_1p_2 \cdots p_k\)라고 쓰자. 단, \(p_i\)들은 서로 다르며, \(2\)거나 \(4k+1\) 꼴 소수다.

페르마의 두 제곱수 정리에 의해, 각 \(p_i\)는 두 제곱수의 합으로 나타낼 수 있다.

라그랑주 항등식에 의해, [두 제곱수의 합으로 나타낼 수 있는 두 자연수의 곱]은 [두 제곱수의 합]으로 쉽게 나타낼 수 있다.

그러니 각 \(p_i\)를 두 제곱수의 합으로 나타내는 방법을 찾으면, 라그랑주 항등식을 반복해서 이용하면 끝난다.

여러 방법이 있지만 나는 이 글에서 소개된 (사진에 있다) Cornaccia's Algorithm을 사용했다. 

사진을 보면 알겠지만 Tonelli-Shanks Algorithm도 필요하다. overflow에 주의하자. int128을 적당히 사용하는 것을 추천.