BOJ 11385 씽크스몰

Table of Contents

📝 문제 정보
#

링크: https://www.acmicpc.net/problem/11385

🧐 관찰 및 접근
#

그냥 FFT의 정의대로, 두 다항식의 곱을 해서 계수들을 구해야한다.
그런데 값이… 너무 많이 커질 수 있다.
$N, M = 1000000$, 모든 $a, b = 1000000$이라면… $f(x) \times g(x)$의 $1000000$차항의 계수는 $10^{18}$이 되는 것 같다.
- 이건 FFT로 하면 실수오차가 너무 심할 것 같은데…
이럴때, NTT를 여러 소수 $p_1, p_2, \cdots$에 대해서 구해두고, 중국인의 나머지 정리를 이용해 원래 계수를 복원하는 방법을 생각할 수 있겠다.
- CRT를 사용하면, $\text{LCM}(m_1, m_2)$ 에 대한 모듈러 값을 얻을 수 있다.
- $p_1 = 998244353, p_2 = 1004535809$을 사용하면 $p_1p_2 > 10^{18}$이므로, 두개면 되겠다.

💻 풀이
#

코드 (C++):

void solve(){
    int N, M; cin >> N >> M; N++; M++;
    vector<int> f(N), g(M);
    rep(i, 0, N) cin >> f[i];
    rep(i, 0, M) cin >> g[i];

    int sz = 1;
    while(sz < N+M) sz <<= 1;

    vector<mint> A1(sz), A2(sz);
    rep(i, 0, N) A1[i] = f[i];
    rep(i, 0, M) A2[i] = g[i];
    FFT::ntt(A1);
    FFT::ntt(A2);
    rep(i, 0, sz) A1[i] *= A2[i];
    FFT::ntt(A1, true);

    vector<mint2> B1(sz), B2(sz);
    rep(i, 0, N) B1[i] = f[i];
    rep(i, 0, M) B2[i] = g[i];
    FFT::ntt(B1);
    FFT::ntt(B2);
    rep(i, 0, sz) B1[i] *= B2[i];
    FFT::ntt(B1, true);

    ll ans = 0;
    rep(i, 0, N+M-1){
        ll r1 = A1[i].val, r2 = B1[i].val;
        auto [x, m] = EGCD::CRT(MOD, r1, MOD2, r2);
        ans ^= x;
    }
    cout << ans;
}

🔒

구현 코드 잠금

아래 쿠팡 링크를 방문하시면 코드가 공개됩니다.
광고 수익이 블로그 운영에 도움이 됩니다 🙏

🛒 쿠팡 방문하고 코드 보기

방문 후 잠금이 자동으로 해제됩니다

📝 문제 정보#

🧐 관찰 및 접근#

💻 풀이#

📝 문제 정보
#

🧐 관찰 및 접근
#

💻 풀이
#