제출 #865801

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
865801		azimanov	수열 (BOI14_sequence)	C++17	42 / 100	1061 ms	138288 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int K = 1 << 20; // check
const double pi = acos(-1);

typedef complex<double> comp;
typedef vector<comp> poly_C;
typedef vector<int64_t> poly;

comp w[K];

bool initialized = 0;
void init_fft() {
    if (initialized) {
        return;
    }
    initialized = 1;
    for (int i = 1; i < K; i *= 2) {
        for (int j = 0; j < i; j++) {
            w[i + j] = polar(1.0, pi * j / i);
        }
    }
}

template <typename T>
void fft(T* in, comp* out, int n, int k = 1) {
    if (n == 1) {
        *out = *in;
        return;
    }
    n /= 2;
    fft(in, out, n, 2 * k);
    fft(in + k, out + n, n, 2 * k);
    for (int i = 0; i < n; i++) {
        comp t = out[i + n] * w[i + n];
        out[i + n] = out[i] - t;
        out[i] += t;
    }
}

void align(poly& a, poly& b) {
    int n = a.size() + b.size() - 1;
    while (a.size() < n) a.push_back(0);
    while (b.size() < n) b.push_back(0);
}

poly_C eval(poly& a) {
    while (__builtin_popcount(a.size()) != 1) {
        a.push_back(0);
    }
    poly_C res(a.size());
    fft(a.data(), res.data(), a.size());
    return res;
}

poly inter(poly_C a) {
    int n = a.size();
    poly_C inv(n);
    fft(a.data(), inv.data(), n);
    poly res(n);
    for (int i = 0; i < n; i++) {
        res[i] = round(inv[i].real() / n);
    }
    reverse(res.begin() + 1, res.end());
    return res;
}

poly mult(poly a, poly b) {
    init_fft();
    align(a, b);
    poly_C A = eval(a);
    poly_C B = eval(b);
    for (int i = 0; i < A.size(); i++) {
        A[i] *= B[i];
    }
    return inter(A);
}

const ll inf = 1e18;
const int C = 10;
const int N = 1e5 + 10;
const int M = 1e6 + 1e5 + 10;

int cnt_suf[C][M];

int flag[N];
ll dp[(1 << C)][(1 << C)];

int flag_true[N + N];
int rig_true[C][N + N];

int b[N];
int lef[C][N], rig[C][N];
int pref[C][N], suf[C][N];

bool getbit(int mask, int bit) {
    return mask & (1 << bit);
}

ll mask_to_ll(int mask) {
    ll res = 0;
    for (int i = 1; i < C; i++) {
        if (getbit(mask, i)) {
            res = res * 10 + i;
            mask ^= (1 << i);
            break;
        }
    }
    for (int i = 0; i < C; i++) {
        if (getbit(mask, i)) {
            res = res * 10 + i;
        }
    }
    return res;
}

void init() {
    {
        for (int x = M - 1; x >= 1; x /= 10) {
            cnt_suf[x % 10][M - 1]++;
        }
    }
    for (int i = M - 2; i >= 1; i--) {
        int mask = 0;
        for (int x = i; x >= 1; x /= 10) {
            mask |= (1 << (x % 10));
        }
        for (int c = 0; c < C; c++) {
            if (getbit(mask, c)) {
                cnt_suf[c][i] = cnt_suf[c][i + 1] + 1;
            } else {
                cnt_suf[c][i] = 0;
            }
        }
    }

    flag[0] = (1 << 0);
    for (int i = 1; i <= N - 1; i++) {
        for (int j = i; j >= 1; j /= 10) {
            flag[i] |= (1 << (j % 10));
        }
        if (i <= 9'999) {
            flag[i] |= (1 << 0);
        }
    }

    flag_true[0] = (1 << 0);
    for (int i = 1; i <= 2 * N - 1; i++) {
        for (int j = i; j >= 1; j /= 10) {
            flag_true[i] |= (1 << (j % 10));
        }
    }

    for (int i = 0; i < (1 << C); i++) {
        for (int j = 0; j < (1 << C); j++) {
            dp[i][j] = inf;
        }
    }
    for (int mask = 0; mask < (1 << C); mask++) {
        for (int last = 0; last < C && last != 9; last++) {
            int pref_mask = mask | (1 << last);
            int suf_mask = mask | (1 << (last + 1));
            if (mask_to_ll(mask) != 0 || last != 0) {
                dp[pref_mask][suf_mask] = min(dp[pref_mask][suf_mask], mask_to_ll(mask == 1 ? 3 : mask) * 10 + last);
            }

            pref_mask = mask | (mask == 0 && last == 0 ? 0 : (1 << last)) | (1 << 9);
            suf_mask = mask | (1 << (last + 1)) | (1 << 0);
            dp[pref_mask][suf_mask] = min(dp[pref_mask][suf_mask], mask_to_ll(mask == 1 ? 3 : mask) * 100 + last * 10 + 9);
        }
    }
    for (int i = (1 << C) - 1; i >= 0; i--) {
        for (int j = (1 << C) - 1; j >= 0; j--) {
            for (int c = 0; c < C; c++) {
                dp[i][j] = min(dp[i][j], dp[i | (1 << c)][j]);
                dp[i][j] = min(dp[i][j], dp[i][j | (1 << c)]);
            }
        }
    }
}

void calc_lef_rig(int k) {
    const int n = 100'000;
    for (int c = 0; c < C; c++) {
        poly p(n, 0);
        poly q(k, 0);
        for (int i = 0; i < n; i++) {
            p[i] = getbit(flag[i], c);
        }
        for (int i = 1; i <= k; i++) {
            q[k - i] = b[i] == c;
        }
        auto r = mult(p, q);
        for (int i = 0; i < n; i++) {
            lef[c][i] = r[i];
            rig[c][i] = r[i + k - 1];
        }
    }
}

void calc_pref_suf(int k) {
    for (int c = 0; c < C; c++) {
        pref[c][0] = 0;
        suf[c][k + 1] = 0;
    }
    for (int i = 1; i <= k; i++) {
        for (int c = 0; c < C; c++) {
            pref[c][i] = pref[c][i - 1];
        }
        pref[b[i]][i]++;
    }
    for (int i = k; i >= 1; i--) {
        for (int c = 0; c < C; c++) {
            suf[c][i] = suf[c][i + 1];
        }
        suf[b[i]][i]++;
    }
}

void calc_rig_true(int k) {
    const int n = 200'000;
    for (int c = 0; c < C; c++) {
        poly p(n, 0);
        poly q(k, 0);
        for (int i = 0; i < n; i++) {
            p[i] = getbit(flag_true[i], c);
        }
        for (int i = 1; i <= k; i++) {
            q[k - i] = b[i] == c;
        }
        auto r = mult(p, q);
        for (int i = 0; i < n; i++) {
            rig_true[c][i] = r[i + k - 1];
        }
    }
}

ll solve_small(int k) {
    const int n = 100'000;
    for (int i = 1; i < n; i++) {
        bool ok = true;
        for (int c = 0; c < C; c++) {
            ok &= rig_true[c][i] == pref[c][k];
        }
        if (ok) {
            return i;
        }
    }
    return inf;
}

ll solve(int k) {
    calc_lef_rig(k);
    calc_rig_true(k);
    calc_pref_suf(k);

    const int n = 100'000;
    ll ans = inf;

    ans = min(ans, solve_small(k));

    for (int i = 0; i < n; i++) {
        if (i + k - 1 < n) {
            int need = 0;
            for (int c = 0; c < C; c++) {
                if (rig[c][i] != pref[c][k]) {
                    need |= (1 << c);
                }
            }
            ans = min(ans, dp[need][0] * n + i);
        } else {
            int len_pref = n - i;
            int len_suf = k - len_pref;
            int need_pref = 0, need_suf = 0;
            for (int c = 0; c < C; c++) {
                if (rig[c][i] != pref[c][len_pref]) {
                    need_pref |= (1 << c);
                }
                if (lef[c][len_suf - 1] != suf[c][k - len_suf + 1]) {
                    need_suf |= (1 << c);
                }
            }
            ans = min(ans, dp[need_pref][need_suf] * n + i);
        }
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif

    init();
    init_fft();

    int k;
    cin >> k;
    for (int i = 1; i <= k; i++) {
        cin >> b[i];
    }

    cout << solve(k) << "\n";

#ifdef LOCAL
    cout << "\nTime elapsed: " << double(clock()) / CLOCKS_PER_SEC << " s.\n";
#endif
}

컴파일 시 표준 에러 (stderr) 메시지

sequence.cpp: In function 'void align(poly&, poly&)':
sequence.cpp:47:21: warning: comparison of integer expressions of different signedness: 'std::vector<long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |     while (a.size() < n) a.push_back(0);
      |            ~~~~~~~~~^~~
sequence.cpp:48:21: warning: comparison of integer expressions of different signedness: 'std::vector<long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |     while (b.size() < n) b.push_back(0);
      |            ~~~~~~~~~^~~
sequence.cpp: In function 'poly mult(poly, poly)':
sequence.cpp:77:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::complex<double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for (int i = 0; i < A.size(); i++) {
      |                     ~~^~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 33 / 33
• Subtask 3: 0 / 25
• Subtask 4: 0 / 33