rkm0959

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

전체의 각 부분집합 \(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을 적당히 사용하는 것을 추천.