[C++] 25456번 궁금한 시프트

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

---

 

26/02/11

 

 

1067번 이동 문제와 매우 유사하다.

---

 

문제 접근 방식:

 

 

문제에서 주어진 코드를 잘 보면, 두 문자열 $S, T$를 각각 $s, t$만큼 offset을 두고, $S[(s+i)\text{mod }N] = T[(t+i)\text{mod }N] = 1$인 경우 cnt값에 1을 더해주는 코드이다.

문제의 요구사항은 cnt의 최댓값을 찾는 것인데, 결국 이것도 1067번 이동 문제와 똑같은 흐름으로 흘러간다.

크기가 $N$으로 같은 두 배열이 주어졌을 때의 최댓값을 구하는 것인데, 여기선 문자열로 주어진 것만 다르다.

이동문제와 마찬가지로, 배열 $S$를 2배 길이로 만들어주고, 배열 $T$를 뒤집어서 FFT한번 수행하면 충분하다.

계수 또한 최대 $500\ 000$이기 때문에 $998\ 244\ 353$으로 NTT를 돌려도 충분하다.

---

아래는 내가 위의 접근 방식과 같이 작성한 C++ 코드이다. 더보기를 누르면 확인할 수 있다.

// 25456번 궁금한 시프트
// NTT
#include <iostream>
#include <vector>

using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
typedef long long ll;

template<int MOD, int G>
struct NTT{
private:
    inline int mul_mod(int a, int b) const {return (ll)a*b%MOD;}
    inline int pow_mod(int a, int e) const {
        int res = 1;
        while (e > 0){
            if (e & 1) res = mul_mod(res, a);
            a = mul_mod(a, a);
            e >>= 1;
        }
        return res;
    }
    inline int mod_inv(int a) const {return pow_mod(a, MOD-2);}
public:
    void iter_NTT(vector<int>& a, int invert){
        int n = (int)a.size();
        for (int i = 1, j = 0; i < n; ++i){
            int bit = n >> 1;
            while (j & bit){
                j ^= bit;
                bit >>= 1;
            }
            j ^= bit;
            if (i < j) swap(a[i], a[j]);
        }
        for (int len = 2; len <= n; len <<= 1){
            int wlen = pow_mod(G, (MOD-1)/len);
            if (invert) wlen = mod_inv(wlen);
            for (int i = 0; i < n; i += len){
                int w = 1;
                for (int j = 0; j < len / 2; ++j){
                    int u = a[i+j];
                    int v = mul_mod(w, a[i+j+len/2]);
                    int x = u+v; if (x >= MOD) x -= MOD;
                    int y = u-v; if (y < 0) y += MOD;
                    a[i+j] = x;
                    a[i+j+len/2] = y;
                    w = mul_mod(w, wlen);
                }
            }
        }
        if (invert){
            int inv = mod_inv(n);
            for (int i = 0; i < n; ++i){
                a[i] = mul_mod(a[i], inv);
            }
        }
    }
    vector<int> convolution(vector<int> a, vector<int> b){
        int Sa = (int)a.size(), Sb = (int)b.size();
        int n = 1;
        while (n < Sa+Sb-1){n <<= 1;}
        a.resize(n); b.resize(n);
        iter_NTT(a, 0); iter_NTT(b, 0);
        for (int i = 0; i < n; ++i){
            a[i] = mul_mod(a[i], b[i]);
        }
        iter_NTT(a, 1);
        a.resize(Sa+Sb-1);
        return a;
    }
};

int main(void){
    fastio

    string S, T;
    getline(cin, S);
    getline(cin, T);
    int N = (int)S.size();
    vector<int> A(2*N, 0), B(N, 0);
    for (int i = 0; i < N; ++i){
        if (S[i] == '1') {
            A[i] = 1;
            A[i+N] = 1;
        }
    }
    for (int i = 0; i < N; ++i){
        if (T[i] == '1'){
            B[N-i-1] = 1;
        }
    }
    NTT<998'244'353, 3> ntt;
    auto C = ntt.convolution(A, B);
    int ans = 0;
    for (int i = N; i < 2*N; ++i){
        ans = max(ans, C[i]);
    }
    cout << ans;
    return 0;
}