BOJ 31939: 멀티버스를 여행하는 성재를 위한 안내서

열시오십칠분이십육초·2025년 11월 4일

https://www.acmicpc.net/problem/31939

문제 해석

먼저 문제를 변형해보자.
임의의 점 $z=re^{i\theta}$ 에서 받는 힘의 크기는

\prod^{N}_{k=1}{|z-\alpha _{k}|}^2,\ \ \alpha_{k}=x_{k}+iy_{k}

이때

Q(z)=\prod^{N}_{k=1}{(z-\alpha _{k})}=\sum ^N _{k=0} C_{k}z^k

라고 두면

𝔼\bigg[\prod^N_{k=1} {|z-\alpha _{k}|}^2 \bigg]=\frac{1}{\pi R^2} \int _{|z| \leq R} {|Q(z)|^2 dA}=\sum ^N _{k=0} {|C_{k}|^2 \frac{R^{2k}}{k+1}}

로 표현할 수 있다. 즉, 문제는 $C_{k}$ 의 제곱값을 구하는 문제로 환원할 수 있다.

증명과 풀이 과정

1. 셋업

천체의 좌표를 $\alpha_{k}=x_{k}+iy_{k} \in \mathbb{C}$ 로 두고
다항식 $Q(z)$ 를 정의하자. (앞서 정리한 것과 같다.) 그러면 임의의 점 $z$ 에서 힘의 크기는 $|Q(z)|^2$ 가 된다. 이제 구할 기댓값은

\mathbb{E}\bigg[|Q(Z)|^2\bigg]=\frac{1}{\pi R^2}\int \int_{|z| \leq R} {|Q(z)|^2 dA(z)}

이때 $Z$ 는 원판 $\{z:|z| \leq R\}$ 위 균등분포이고, $dA$ 는 2차원 면적 요소를 의미한다.
$Q$ 는 다항식이므로 $|Q|^2$ 은 연속이고 유계함수이며, 원판이 유한 영역이므로 유한합과 적분의 교환이 정당하다.

2. 직교성

다항식의 제곱 절댓값을 전개하면

|Q(z)|^2=\bigg(\sum ^N _{k=0} C_{k} z^k\bigg)\bigg(\sum ^N _{l=0} \bar{C}_{l} \bar{z}^l\bigg)=\sum ^N _{k,\ l=0} C_{k}\bar{C}_{l} z^k\bar{z}^l

따라서

\int \int_{|z| \leq R}|Q(z)|^2dA=\sum ^N _{k,\ l=0} C_{k}\bar{C}_{l}\int\int_{|z| \leq R}z^k\bar{z}^ldA

이제 원판에서의 단항식 직교성을 계산한다. 극좌표 $z=re^{i\theta}$ 에서

z^k\bar{z}^l=r^{k+l}e^{i(k-l)\theta},\ \ dA=r\ dr\ d\theta

즉,

\begin{aligned} \int\int_{|z| \leq R}z^k\bar{z}^ldA &=\int^R_{0}\int^{2\pi}_{0}r^{k+l}e^{i(k-l)\theta}r\ dr\ d\theta\\ &=\bigg(\int^R_{0}r^{k+l+1}dr\bigg)\bigg(\int^{2\pi}_{0}e^{i(k-l)\theta}d\theta\bigg) \end{aligned}

이때

\int^{2\pi}_{0}{e^{i(k-l)\theta}d\theta}= \begin{cases} 1 & k=l \\ 0 & k \not= l \end{cases}

이므로 (푸리에함수의 완전직교성)

\int\int_{|z|\leq R}z^k\bar{z}^ldA =\delta_{kl} \ \cdot\ 2\pi\int^R_{0}r^{2k+1}dr =\delta_{kl}\ \cdot\ \pi\frac{R^{2k+2}}{k+1}

즉 원판에서 $z^k$ 들은 서로 직교한다.

3. 기댓값의 닫힌형

직교성으로 교차항이 모두 사라지므로

\int\int_{|z|\leq R}|Q(z)|^2dA =\sum ^N _{k=0} |C_{k}|^2\ \cdot\ \pi\frac{R^{2k+2}}{k+1}

원판 평균을 취하면

\mathbb{E}\bigg[|Q(Z)|^2\bigg] =\frac{1}{\pi R^2} \int\int_{|z|\leq R}|Q(z)|^2dA =\sum ^N _{k=0} |C_{k}|^2 \ \cdot\ \frac{R^{2k}}{k+1}

답은 어떻게 구하나?

$Q(z)$ 의 계수 $C_{k}=a_k+b_k$ 를 구하면
$|C_k|^2=a_k\ ^2+b_k\ ^2$ 를 통해 문제를 해결할수 있다.
이제 다시 유한곱 꼴로 돌아와서, 각 선형인수 $(z-\alpha_k)$ 를 계수가 $\mathbb{F}_p[k]$ 인 다항식으로 보자.
이때 $(z-\alpha_k)=(1,\ 0)z+(-x_k,\ -y_k)$ 로 두고 이것을 분할정복을 통해 product tree의 형태로 곱해주면 된다. 다항식 곱셈은 NTT를 사용하면 된다.

그러면 두 복소 다항식을 어떻게 NTT로 곱한다는걸까? 그 답은 간단하다. 두 다항식 $\text{Re}[i]$ , $\text{Im}[i]$ 을 한 개의 구조체로 묶어 복소 연산을 적용하면 된다. 이는 3번의 NTT로 해결할 수 있는데,

A(z)=A_0(z)+iA_1(z),\ \ B(z)=B_0(z)+iB_1(z)

A \cdot B=(A_0B_0-A_1B_1) + i(A_0B_1+A_1B_0)

와 같이 두고,

\begin{aligned} S_1&=A_0 * B_0 \\ S_2&=A_1 * B_1 \\ S_3&=(A_0+A_1) * (B_0+B_1) \end{aligned}

세 가지의 합성곱을 구해주면, $C(z)=C_0+iC_1$ 을 다음과 같이 구할 수 있다.

\begin{aligned} C_0&=S_1-S_2 \\ C_1&=S_3-S_1-S_2 \end{aligned}

그 구현은 다음과 같다.

struct CPoly {
    vector<int> rea, ima;
    CPoly(int n) {
        rea.assign(n, 0);
        ima.assign(n, 0);
    }
    size_t size() const { return rea.size(); };
    void resize(size_t n) {
        rea.assign(n, 0);
        ima.assign(n, 0);
    };

    CPoly operator*(const CPoly &o) const {
        auto S1=ntt.conv(rea, o.rea);
        auto S2=ntt.conv(ima, o.ima);
        vector<int> A(size()), B(o.size());
        for (int i=0; i<size(); i++) A[i]=(1LL*rea[i]+ima[i])%MOD;
        for (int i=0; i<o.size(); i++) B[i]=(1LL*o.rea[i]+o.ima[i])%MOD;
        auto S3=ntt.conv(A, B);
        int n=S3.size();
        CPoly C(n);
        for (int i=0; i<n; i++) {
            C.rea[i]=(1LL*S1[i]-S2[i]+MOD)%MOD;
            C.ima[i]=(1LL*S3[i]-S1[i]-S2[i]+MOD*2)%MOD;
        }
        return C;
    }
};

CPoly make(int a, int b) {
    CPoly P(2);
    P.rea[0]=(MOD-a)%MOD;
    P.ima[0]=(MOD-b)%MOD;
    P.rea[1]=1;
    P.ima[1]=0;
    return P;
}

열시오십칠분이십육초

<(╹ヮ╹)>