[C++] 30977번 금강산도 식후경

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

---

 

26/02/15

 

 

문제의 접근 방법이 그리 어렵지 않은 문제이다.

---

 

문제 접근 방식:

 

 

문제가 뭐라고 길게 쓰여있지만, 주어진 수를 중복 포함하여 여러번을 뽑아 합을 만드는 경우의 수를 구하는 문제로 귀결된다.

이런 문제들은 우리가 이전에 정말 많이 해결했던 문제들이다.

다항식 배열을 만들고 해당 배열을 $M$제곱하면 된다.

문제를 잘 읽어보면 이제 문자열 매칭으로 넘어간다는 사실을 알 수 있다.

인접한 $D_{i}$끼리의 차 배열과 인접한 $F_{i}$끼리의 차 배열을 만들어서 두 배열을 매칭으로 비교하면 된다.

KMP를 써도 되고 라빈카프 써도 되는데, 나는 라빈카프로 했다.(바로 짤 수 있는게 그것뿐이어서...)

여러 번 시행착오를 겪었다.

2번의 시간초과를 받았다. NTT가 i128과 long long으로 구현되어있어서 long long과 int로 바꾸는 최적화를 진행했다.

이후 4번의 WA를 받았는데, 배열끼리 비교하는데 인접한 $D_{i}$끼리의 차 배열이 아니라 그냥 $D_{i}$ 배열을 사용해서 4번의 WA를 받았다.

---

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

// 30977번 금강산도 식후경
// FFT, 해싱
/*
접근 방법:
FFT로 모든 부분 수열 만들고 해싱 갈기면 될듯
*/
#include <iostream>
#include <vector>

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

/*
Notes:
MOD = 998'244'353 = 119*2^23 + 1
MOD = 1'004'535'809 = 479*2^21 + 1 / G = 3 / Works for lengths up to 2^21. / Use with CRT and 998'244'353
MOD = 469'762'049 = 7*2^26 + 1 / G = 3 / Works for lengths up to 2^26.
MOD = 167'772'161 = 5*2^25 + 1 / G = 3 / Works for lengths up to 2^25.
MOD = 1'224'736'769 = 73*2^24 + 1 / G = 3 / Works for lengths up to 2^24.
Combine above 3-NTT primes with CRT -> 75bits fast product ok.
*/
// NOTE THAT FOR FAST WORKING, CHANGE i128 -> int, int -> int
template<int MOD, int G>
struct NTT {
private :
    // HELPER FUNCTION
    inline int mul_mod(int a, int b) const {return (long long)a * b % MOD;}
    inline int pow_mod(int a, int e) const {
        int r = 1;
        while(e > 0){
            if(e & 1) r = mul_mod(r, a);
            a = mul_mod(a, a);
            e >>= 1;
        }
        return r;
    }
    inline int mod_inv(int a) const {return pow_mod(a, MOD-2);}
public : 
    void iterative_NTT(vector<int>& a, int invert){
        int n = (int)a.size();
        // 1) bit-reversal permutation
        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]);
        }
        // 2) butterflies by length = 2, 4, 8, ...
        for (int len = 2; len <= n; len <<= 1){
            // primitive len-th root of unity
            int w_len = pow_mod(G, (MOD - 1) / len);
            if (invert) w_len = mod_inv(w_len);
            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, w_len);
                }
            }
        }
        // 3) Divide by n (multiply by inverse) for inverse transform
        if (invert){
            int inv_n = mod_inv(n);
            for (int i = 0; i < n; ++i){
                a[i] = mul_mod(a[i], inv_n);
            }
        }
    }
    // Input : Coefficient vector {a_0, a_1, ...}, {b_0, b_1, ...}
    // Output : Convolution of two coefficient vector
    vector<int> convolution(vector<int> a, vector<int> b) {
        if (a.empty() || b.empty()) return {};
        int S_a = (int)a.size(), S_b = (int)b.size();
        // Make vector size easy to dnc(2^n).
        int n = 1;
        while (n < S_a + S_b - 1){
            n <<= 1;
        }
        a.resize(n); b.resize(n);
        // Normalize to [0, MOD)
        for (int i = 0; i < n; ++i){
            a[i] %= MOD; if (a[i] < 0) a[i] += MOD;
            b[i] %= MOD; if (b[i] < 0) b[i] += MOD;
        }
        // NTT
        iterative_NTT(a, 0); iterative_NTT(b, 0);
        // Pointwise product
        for (int i = 0; i < n; i++) {
            a[i] = mul_mod(a[i], b[i]);
        }
        // INTT
        iterative_NTT(a, 1);
        a.resize(S_a + S_b - 1);
        return a;
    }
};

inline void cutoff_vector(vector<int>& a){
    for (int i = 0; i < a.size(); ++i){
        if (a[i] > 0) a[i] = 1;
    }
    return;
}

vector<int> poly_pow(vector<int> poly, int e){
    NTT<998244353, 3> ntt;
    vector<int> ret = {1};
    while(e > 0){
        if(e & 1){
            ret = ntt.convolution(ret, poly);
            cutoff_vector(ret);
        }
        poly = ntt.convolution(poly, poly);
        cutoff_vector(poly);
        e >>= 1;
    }
    return ret;
}

int main(void) {
    fastio

    int N, M, K; cin >> N >> M >> K;
    vector<int> T(1'001, 0);
    int Ti;
    for (int i = 0; i < N; ++i){
        cin >> Ti;
        T[Ti] = 1;
    }
    auto ret_poly = poly_pow(T, M);
    vector<int> food;
    for (int i = 0; i < ret_poly.size(); ++i){
        if (ret_poly[i]) food.push_back(i);
    }
    vector<int> diff;
    for (int i = 0; i < food.size()-1; ++i){
        diff.push_back(food[i+1]-food[i]);
    }
    int before, Di; cin >> before;
    vector<int> D;
    for (int i = 0; i < K-1; ++i){
        cin >> Di;
        D.push_back(Di - before);
        before = Di;
    }
    if (D.size() > diff.size()){
        cout << 0; return 0;
    }
    long long MOD = 2147483659LL;
    long long BASE = 13LL;

    long long target = 0;
    long long t = 1;
    for (int i = 0; i < D.size(); ++i){
        target = (((target*BASE) % MOD)+((long long) D[i])) % MOD;
        t = (t*BASE) % MOD;
    }
    long long hashval = 0;
    for (int i = 0; i < D.size(); ++i){
        hashval = (((hashval*BASE) % MOD)+((long long) diff[i])) % MOD;
    }
    long long ans = 0;
    if (target == hashval) ++ans;
    for (int i = D.size(); i < diff.size(); ++i){
        if (((hashval*BASE) % MOD) < ((t*diff[i-D.size()]) % MOD)){
            hashval = ((hashval*BASE) % MOD) - ((t*diff[i-D.size()]) % MOD) + MOD;
        } else {
            hashval = ((hashval*BASE) % MOD) - ((t*diff[i-D.size()]) % MOD);
        }
        hashval = (hashval + diff[i]) % MOD;
        if (target == hashval) ++ans;
    }
    cout << ans;
    return 0;
}