📝 문제 정보#
🧐 관찰 및 접근#
- 0과 1로 이루어진 두 문자열 $S, T$가 주어진다.
- 두 문자열에 시프트 연산이 가능하다고 할때, 합성곱의 최댓값을 구하자.
- 합성곱이므로 FFT를 의심해볼 수 있겠다.
- 0과 1로 이루어진 문자열을 다항식으로 해석하면 된다.
- 곱 결과가 같은 차수에 올 수 있도록 한 다항식의 계수들을 뒤집고, 시프트 연산을 위해 둘중 한 배열을 두배로 늘려서 계산하자.
💻 풀이#
- 코드 (C++):
void solve(){
string S, T;
cin >> S >> T;
int N = S.size();
int sz = 1;
while(sz < 3*N) sz <<= 1;
vector<cd> A(sz), B(sz);
rep(i, 0, N) if(S[i] == '1') A[i] = 1;
rep(i, 0, N) if(S[i] == '1') A[i+N] = 1;
rep(i, 0, N) if(T[i] == '1') B[N-1-i] = 1;
FFT::fft(A);
FFT::fft(B);
rep(i, 0, sz) A[i] *= B[i];
FFT::fft(A, true);
int ans = 0;
rep(i, N-1, 2*N-1) ans = max(ans, (int)round(A[i].real()));
// rep(i, 0, 3*N) cout << i << ' ' << A[i] << '\n';
cout << ans << '\n';
}