By MilkClouds in PS — 2022년 3월 13일

3월의 PS일지(1/2선)

특정 위치의 피보나치 수를 다른 수로 고정하는 것을, 3x3 행렬을 이용함으로써 해결한다. $(F_{i-1}, F_{i-2}, 1)^T$의 열벡터가 있을 때,

\[\left(\begin{matrix}0 & 0 & B[i] \\ 1 & 0 & 0 \\ 0 & 0 & 1\end{matrix}\right)\]

를 곱하면 $(B[i], F_{i-1}, 1)^T$의 열벡터가 나온다. 이는 $F_{i}$를 $B[i]$로 고정하는 효과를 낸다. 통상 피보나치 수를 계산할 때 2x2의 행렬을 이용해 $(F_i, F_{i-1})$의 2개 원소만을 고려하는데, 이 둘만으로는 이전 수열 값과 독립적인 특정 값으로 다음 값을 고정시킬 수 없다. 특정 위치의 값을 특정 값으로 '고정'하기 위해 여분의 차원에 성분 $1$를 첨가한다고 생각하면 된다.

$n=1, \ldots , N$에 대해 $n$번째 수에서 $n+1$번째 수로 이동할 때 곱해야 하는 행렬을 세그먼트 트리에 저장한 후, 세그먼트 트리의 원소를 하나씩 바꿔가다 root의 원소를 출력하는 것으로 문제를 풀 수 있다.

harmonic lemma를 이용하긴 하는데.. 나머지 연산 $A%B$를 $A-B(A/B)$로 바꿔버리고 $B, A/B$의 값이 $B=\sqrt{A}$를 기점으로 어느 한쪽이 희박하게 나타남을 이용한다. 자세한 풀이는 공식 editorial을 참고하자.

일단 먼저 좌측에서 우측으로 읽는 것을 전제로 한다.

여는 괄호 $O$를 하나 없애더라도, 우측으로 갈 때 임의의 지점에서 해당 지점까지 열린 괄호 개수가 닫힌 괄호보다 적은 경우가 없다면, $O$를 지워도 된다.

대충 소스코드로 위의 과정을 나타내면 아래와 같다. 물론 이건 좌측에서 우측으로 가며 여는 괄호만 고려한 것이고, 주어진 문자열을 뒤집은 후 같은 과정을 반복한 결과를 더해야 원래 문자열의 닫는 괄호도 고려할 수 있다.

int solve(){
    int k = 0, ret = 0;
    rep(i, 0, S.length()){
        k += (S[i] == '(') - (S[i] == ')');
        A[i] = k;
    }
    B[S.length() - 1] = A[S.length() - 1];
    rep2(i, 0, S.length() - 1){
        B[i] = min(B[i + 1], A[i]);
    }
    rep(i, 0, S.length()){
        if(S[i] == '(') ret += B[i] == 1;
    }
    return ret;
}

Centroid decomposition + FFT 문제이다. (두 문제는 자매품이다)

어떤 centroid에서 다른 정점으로 가는 거리를 구한 후, 이를 기반으로 다항식을 만든다. centroid에서 거리 $d$인 정점의 개수를 계수로, $d$를 차수로 하여 $A=a_0+a_1 x+a_2x^2+\ldots$를 만든다. 이 다항식은 임의의 정점에서 centroid까지 갈 때 경우의 수와 거리를 나타낸다. 이 다항식을 제곱하여 $A^2$를 구하면 임의의 정점에서 centroid를 거쳐 임의의 정점으로 갈 때 경우의 수와 거리를 구할 수 있다.

다만 이렇게 하면 centroid에서 같은 방향으로 떨어진 두 정점 사이 거리는 잘못 고려하게 된다. 예를 들어 centroid에서 $i$만큼 떨어진 정점과 $j$만큼 떨어진 정점이 centroid에서 같은 방향으로 떨어져 있어 실제 둘의 거리는 $i+j$보다 작더라도(더 엄밀하게 말하면, $i,j$의 LCA가 centroid가 아니더라도), 위의 convolution 과정에서는 반드시 $i$ 정점에서 centroid를 거쳐 $j$로 가는 것만을 고려하므로 거리가 $i+j$가 된다. 따라서 centroid에서 각각의 방향으로 갈 때 경우의 수와 거리를 나타낸 다항식 $B$가 있을 때, $B^2$를 구해서 $A^2$에서 빼줘야 한다. 정리하면 $A^2-\sum_{\text{for child of centroid}} B^2$가 되겠다. 물론 여기에 centroid에서 임의의 정점으로 갈 때의 거리 정보 $A$도 더해줘야 하는데, $A^2-\sum B^2$ 꼴에서는 $(i, j)$ 정점 쌍이 $(j, i)$까지 2번 고려되었으므로 $2A$를 더해야 할 것이다. 요약하면 $2A + A^2-\sum_{\text{for child of centroid}} B^2$가 되고, 답을 출력할 때는 2를 나눠주면 된다.

그리고 centroid에서 같은 방향으로 떨어진 두 정점 사이 거리 정보는 계산이 안됐으므로, centroid를 기점으로 모든 방향으로 트리를 나눈 후에 각각에 대해 똑같은 작업을 반복해야 한다.

다만 이 때 centroid가 아니라 다른 정점을 대충 골랐다간 분할정복이 제대로 이루어지지 않으며 시간복잡도가 급격히 상승할 것이다. 그래서 centroid decomposition을 통해 centroid를 계속 골라줘야 한다.

아래 링크 참고

아래 링크 참고

이분탐색 도중 첫번째 단계에서 만나는 중앙의 노드, 두번째 단계에서 만나는 2개의 노드, 세번째 단계에서 만나는 4개의 노드, 이런 순서로 이진트리(BST)를 만든다. 이후 노드-자식 관계에서 일정 횟수 대소관계가 만족되도록 부등식을 여러개 세우면 된다.

통상의 BST와는 다르게, 대소관계가 left child<node<right child로만 설정되기만 하면 안되고, 적절히 left1 child<node, left2 child<node와 같은 관계가 끼어있어야 한다. 이런 경우 left1 child와 left2 child에는 우위가 없으니 대충 아무거나 먼저 작은 수를 할당해 주면 된다.

통상 BST에서 대소관계가 하나만 다른 BST는 그냥 아무거나 자식이 하나 이상 있는 노드를 잡아 자식 위치를 left에서 right, 또는 right에서 left로 옮겨주면 되는 일이므로 어렵지 않고, 대소관계가 여럿 다르더라도 위의 과정을 반복해 이러한 BST를 제작 가능할 것이므로 NO를 출력하는 경우는 없다.

Harmonic Lemma을 활용해 쉽게 풀 수 있는 문제다.

위와 마찬가지로 Harmonic lemma을 이용해 푸는 문제이다. 다만, $i$가 작을 때는 $j=N/(N/i)$ 연산을 해봐야 $i$가 $i+1$로 한칸밖에 이동하지 않는데 무거운 나눗셈 연산을 두번이나 하므로 손해다. $i$가 작을 때는 $i+1$로 한칸씩 이동하고 나눗셈 연산을 하지 않는 방식으로 연산량을 줄일 수 있다.

TC가 여러 종류인데, 케이스 분류 없이 하나의 솔루션으로는 모든 TC가 풀리지 않아 할 수 없이 2가지 경우로 나눠 풀었다.

multipoint evalution 문제이다. query에 대해 $\prod (x-x_i)$를 이진 트리로 만들어두고 루트에서부터 차례대로 다항식을 나눠가며 나머지를 구한다. 자세한 풀이는 아래 링크 참고.

Dirichlet convolution에 대해, $\phi *1=\text{Id}$이고, $1$의 역원인 $\mu$(뫼비우스 함수)를 양변에 씌우면 $\phi=\text{Id}*\mu$이다. 이를 이용해 식을 잘 정리하면 $\sum_d \phi(d) \prod_i \frac{N_i}{d}$ 꼴이 나온다.

수식 전개는 https://ahgus89.github.io/algorithm/Möbius-inversion/ 아니면 https://hrothgar.tistory.com/144 참고

바로 윗 문제의 진화형이다. harmonic lemma($\frac{n}{i}$ 꼴의 식이 $2\sqrt{n}$개 정도의 함숫값만을 가짐)을 이용해 함숫값이 변하는 지점을 모두 저장해두고 차례대로 처리하면 풀릴 줄 알았지만 그렇게 하면 메모리 초과가 난다. $k=1, \ldots, \sqrt{n}$정도까지, 초기 범위를 저장해 두지 말고 차례대로 처리해야 메모리 초과가 나지 않는다.

$P_n$의 대해 특성방정식의 두 해는 $\varphi, \varphi^{-1}$으로 $F_n$과 똑같다. 따라서 $\varphi^{n}, \varphi^{-n}$의 선형결합으로 $P_n$을 나타낼 수 있다.

\[P_n=a \varphi^n + b\varphi^{-n}\]

위와 같이 두고 $P_0, P_1$을 이용해 $a,b$ 계수를 구해주면 $P_n=\varphi^n$라는 사실을 알 수 있다. 이를 이용해 주어진 수식을 정리하면:

\[P_n^k=\varphi^{nk}=P_{nk}=F_{nk} \varphi + F_{nk-1} \\ P_n^k=A\varphi^k+B=AP_k+B=A(F_k \varphi+F_{k-1})+B\]

위 두 수식의 우변을 보면, $\varphi$를 제외한 모든 계수(피보나치 수, $A, B$)는 정수이다. 따라서 두 수식을 같다고 두고 정리하면

\[AF_k \varphi + AF_{k-1}+B = F_{nk}\varphi + F_{nk-1} \\ \therefore AF_k=F_{nk} , AF_{k-1}+B=F_{nk-1}\]

정리하면 $A=\frac{F_{nk}}{F_k}, B=F_{nk-1}-AF_{k-1}$이다. $F_{nk}$는 $F_{k}$의 배수이므로, 미리 가정했던 대로 훌륭히 정수 $A, B$가 법 $10^9+7$ 위에서 나오는 것을 알 수 있다.

단 이 문제는 그냥 이렇게 두고 풀면 $F_{nk}, F_k$가 모두 법 $10^9+7$ 위에서 0이 되는 경우가 생긴다. $0/0$ 꼴의 극한이 분자와 분모가 모두 0으로 감에도 극한값이 0이 아닐 수 있는 것처럼(안 비슷한가?), 이 문제에서도 분자 $F_k$와 분모 $F_{nk}$가 모두 $p$의 배수가 되어 전체 식의 값이 0이 아님에도 $0/0$ 꼴이 나온다.

이를 해결하기 위해 $p^2$ 위에서 $F_{nk}, F_{k}$를 구한 후, 만약 하나라도 $p$의 배수라면 둘을 $p$로 나눈 후에 법 $p$ 위에서 역원을 구해 나눗셈을 해야 한다.

$S$가 원래 문자열일 때, 변환 연산을 거치면 $S^RS$가 된다. ($S^R$은 $S$의 $0,1$을 reverse한 문자열)

$S$에서 0이 연속한 구간의 개수가 $n$개, 1이 연속한 구간의 개수가 $m$개일 때, $S^R$과 $S$의 경계선에서 0이 겹치지 않는다면 $S^RS$에서 0이 연속한 구간의 개수는 $n+m$개가 된다. 0이 겹친다면 $n+m-1$개가 된다.

결론적으로 $A, B = A+B, A+B-(i\%2)$ 연산을 계속 시행하면 되고, 근데 $n=1000$이면 biginteger 없는 언어는 자릿수 올림을 배열로 구현해야 할 듯하다. 난 간편하게 파이썬으로 풀었다.

Chirp Z-Transform을 써야 한다. FFT를 하는 방법으로는 쿨리-터키 알고리즘(버터플라이)뿐만 아니라 Bluestein's Algorithm도 존재하고, 이것을 이용하면 $N \times N$ cyclic convolution이 가능하다는 전제 하에 임의의 크기의 배열에 대해 FFT를 할 수 있다.

또 단위 복소수 $w$ 대신 임의의 $z$에 대해 FFT를 수행할 때 이를 Z-transform이라 한다.

// reference: https://codeforces.com/blog/entry/83532, https://cp-algorithms.com/algebra/polynomial.html#chirp-z-transform
void chirp_z(vector<ll>& f, ll w){
    int N = f.size();
    vector<ll> a(N * 2), b(N);
    for(ll i = 0; i < 2 * N; i++) a[i] = dp[safe_mod(i * (i - 1) / 2)];
    for(ll i = 0; i < N; i++){
        b[N - 1 - i] = f[i] * dp[safe_mod(-i * (i - 1) / 2)] % MOD;
    }
    auto&& ret = convolution(a, b);
    for(ll i = 0; i < N; i++){
        f[i] = dp[safe_mod(-i * (i - 1) / 2)] * (ret[N - 1 + i] % MOD) % MOD;
    }
}

아주 악독한 문제다. Big-O에 따른 시간복잡도도 적당히 맞춰서 분명 이 정도면 통과되겠지? 싶은 소스코드를 제출했는데 고쳐봐도 계속 TLE가 나와서.. 내 나름의 극한의 최적화를 한 다음에야 겨우 통과했다.

$\Z/2\Z$ 위에서 $P(x)^2=P(x^2)$이다. ($P(x)=a_0 x_0+a_1x_1+ \cdots$라고 생각하면, 자기 자신과 제곱한 항은 그대로 남아있는데 다른 항이랑 곱해진 항은 계수 2가 곱해지므로 $\Z/2\Z$ 위에서 사라진다. $(a+b+c)^2=a^2+b^2+c^2+2(ab+bc+ca)$임을 상기하자.)

이를 이용해 $P(x)^{2k}$와 $Q(x)$의 곱은 $Q(x)$를 홀수번째 항과 짝수번째 항으로 분리해 독립적으로 처리할 수 있다. $P(x)^{2k}$는 어차피 짝수차수항만 가지고 있기 때문이다. $Q(x)=R(x^2)+xS(x^2)$일 때, $P(x)^{2k}Q(x)=P(x)^{2k}R(x^2)+xP(x)^{2k}S(x^2)=P(x^2)^{k}R(x^2)+xP(x^2)^{k}S(x^2)$이고, $P(x^2)^{k}R(x^2)$와 $P(x^2)^{k}S(x^2)$를 따로 처리하면 된다.

$P(x)^{2k+1}Q(x)$은 그냥 $P(x)^{2k} \cdot (P(x)Q(x))$로 분리하면 된다.

수식을 잘 전개하자.

수식을 잘 전개하자.

수식을 더 잘 전개하자. 너무 길어서 여기 타이핑하기는 좀 심각하게 귀찮다...

You might also like...