BOJ 19265 - Is it a p-drome?

문제 링크 : https://www.acmicpc.net/problem/19265

문제 풀이

 이 문제는 배열 p에 존재한 모든 $p_i$에 대해서 $T_i = Tp_i $ 인지를 S의 모든 구간에 T에 대해서 확인하는 문제이다. 

 여기서 어떤 형태를 비교하는 거니까 문자열 매칭과 비슷한 느낌을 받을 수 있다. 먼저 생각난 것은 KMP 였지만 KMP로는 풀 수 없는 형태였다. 실패함수가 좋은 형태로 나타나지 않기 때문에 KMP는 포기할 수 밖에 없었다. 

 이 상태에서 문제를 푸는 사고의 흐름이었다면 라빈-카프 해싱을 생각을 했어야 했다. $T_i = Tp_i $ 라는 것은 i 기반 해싱값과 pi 기반 해싱값이 같다는 거고, 좀 만 더 생각하고 식을 변형 시켜 보면 $\sum_{i}^{} i\times T_i = \sum_{i}^{} p_i\times T_i$ 이어야만 구간이 문제 조건을 만족한다는 것을 알 수 없다. 하지만 이 식을 만족해도 문제 조건을 만족한다는 보장이 없기 때문에 $ \sum_{i}^{} A_i\times i\times T_i = \sum_{i}^{}A_i\times p_i\times T_i $ 의 식으로 확장시켜서 생각할 수 있고, 이 식에서는 $A_i$ 라는 변수를 추가되었고 이를 마음대로 변형시켜서 여러 번 확인하는 것을 할 수 있다. 

하지만 문제가 있다. S의 모든 길이 m의 부분 구간 T에 대해서 위의 식의 좌변 과 우변의 값을 계산해야 한다. 이때 T의 길이가 m이며 sliding 한 형태로 존재한다는 것을 이용하여 FFT를 떠올릴 수 있다. T에 곱해질 값을 순서를 뒤집은 다음에 두 다항식을 곱하게 되면 위의 한 쪽 변이 곱해진 다항식의 한 항의 계수로써 등장하게 된다. 따라서 $O(N^2)$ 이 아닌 $O(NlgN)$ 에 문제를 해결 할 수 있다. 

나는 해싱을 생각을 못했기 때문에 FFT 라는 단어를 힌트로 들었고, 조건을 다른 형태의 식으로 바꾸었다. $ \sum_{i}^{} A_i\times T_i = 0 $ 를 확인할 건데 $A_i$  를 구성할 때   $A_i$ 에 k를 더하고 $A_pi$ 에 -k를 하는 것을 무작위 적으로 반복하면 위의 식을 만족해야 문제의 조건을 만족한다고 할 수 있다. 이를 이용하여 똑같이 A 배열을 구성하고 fft를 돌려서 시간복잡도를 맞추어 주면 문제를 해결 할 수 있다. 아래의 코드는 이 풀이 기반 코드이다.  

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef double dl;
typedef pair<dl,dl> pdi;
typedef pair<ll,ll> pii;
typedef pair<ll,pii> piii;
 
#define ff first
#define ss second
#define eb emplace_back
#define ep emplace
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) lower_bound(all(v), x) - v.begin()
//cout<<fixed;
//cout.precision(12);
 
struct poi{
    ll val,xx,yy;
};
 
 
namespace fft{
    using real_t = double;
    using cpx = complex<real_t>;
    void FFT(vector<cpx> &a, bool inv_fft = false){
        int N = a.size();
        vector<cpx> root(N/2);
        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]);
        }
        real_t ang = 2 * acos(-1) / N * (inv_fft ? -1 : 1);
        for(int i=0; i<N/2; i++) root[i] = cpx(cos(ang * i), sin(ang * i));
        for(int i=2; i<=N; i<<=1){
            int step = N / i;
            for(int j=0; j<N; j+=i){
                for(int k=0; k<i/2; k++){
                    cpx u = a[j+k], v = a[j+k+i/2] * root[step * k];
                    a[j+k] = u+v;
                    a[j+k+i/2] = u-v;
                }
            }
        }
        if(inv_fft) for(int i=0; i<N; i++) a[i] /= N;
    }
    vector<ll> multiply_mod(const vector<int> &a, const vector<int> &b, const int mod){
        int N = 2; while(N < a.size() + b.size()) N <<= 1;
        vector<cpx> v1(N), v2(N), r1(N), r2(N);
        for(int i=0; i<a.size(); i++) v1[i] = cpx(a[i] >> 15, a[i] & 32767);
        for(int i=0; i<b.size(); i++) v2[i] = cpx(b[i] >> 15, b[i] & 32767);
        FFT(v1); FFT(v2);
        for(int i=0; i<N; i++){
            int j = i ? N-i : i;
            cpx ans1 = (v1[i] + conj(v1[j])) * cpx(0.5, 0);
            cpx ans2 = (v1[i] - conj(v1[j])) * cpx(0, -0.5);
            cpx ans3 = (v2[i] + conj(v2[j])) * cpx(0.5, 0);
            cpx ans4 = (v2[i] - conj(v2[j])) * cpx(0, -0.5);
            r1[i] = (ans1 * ans3) + (ans1 * ans4) * cpx(0, 1);
            r2[i] = (ans2 * ans3) + (ans2 * ans4) * cpx(0, 1);
        }
        FFT(r1, true); FFT(r2, true);
        vector<ll> ret(N);
        for(int i=0; i<N; i++){
            ll av = llround(r1[i].real());
            ll bv = llround(r1[i].imag()) + llround(r2[i].real());
            ll cv = llround(r2[i].imag());
            av %= mod, bv %= mod, cv %= mod;
            ret[i] = (av << 30) + (bv << 15) + cv;
            ret[i] %= mod;
            ret[i] += mod;
            ret[i] %= mod;
        }
        return ret;
    }
}
 
vector<int> x;
ll n,m;
ll mod=998244353;
string s;
string t;
ll arr[1010101];
ll brr[1010101];
vector<ll> v[1010101];
vector<int> an;
vector<ll> res;
 
 
mt19937 rd((unsigned)chrono::steady_clock::now().time_since_epoch().count());
int grnd(ll a,ll b){
    uniform_int_distribution<int> rnd(a, b);
    return rnd(rd);
}
 
ll ans[1010101];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll i,j,k,a,b,c,d,e,f;
    cin>>n>>m>>k;
 
    for(i=1;i<=n;i++){
        ll idx=n-i;
        cin>>a;
        arr[idx]=n-a;
    }
 
    for(i=1;i<=m;i++){
        cin>>a;
        an.pb(a);
    }
    for(i=0;i<=m+n;i++){
        ans[i]=1;
    }
 
    for(ll p=1;p<=3;p++){
        x.clear();
        x.resize(n);
 
        for(i=1;i<=7*n;i++){
            ll f=grnd(0,n-1);
            ll val=grnd(1,p*100);
            x[min(f,arr[f])]+=val;
            x[max(f,arr[f])]-=val;
        }
 
        res=fft::multiply_mod(x, an, 998244353);
        for(i=n-1;i<m;i++){
            if(res[i]) ans[i]=0;
        }
    }
 
    for(i=n-1;i<m;i++){
        cout<<ans[i];
    }
 
}