📝 문제 정보
🧐 관찰 및 접근
- 그냥 FFT의 정의대로, 두 다항식의 곱을 해서 계수들을 구해야한다.
- 그런데 값이… 너무 많이 커질 수 있다.
- $N, M = 1000000$, 모든 $a, b = 1000000$이라면… $f(x) \times g(x)$의 $1000000$차항의 계수는 $10^{18}$이 되는 것 같다.
- 이건 FFT로 하면 실수오차가 너무 심할 것 같은데…
- 이럴때, [[260406_TIL_NTT(Number Theoretic Transform) - 정수론적 변환|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;
}