oj.uz

Submission #865797

# Submission time Handle Problem Language Result Execution time Memory
865797 2023-10-24T16:16:09 Z azimanov Sequence (BOI14_sequence) C++17
100 / 100
 968 ms 80676 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

template<int mod>
class Modular {
public:
    int val;
    Modular() : val(0) {}
    Modular(int new_val) : val(new_val) {
    }
    friend Modular operator+(const Modular& a, const Modular& b) {
        if (a.val + b.val >= mod) return a.val + b.val - mod;
        else return a.val + b.val;
    }
    friend Modular operator-(const Modular& a, const Modular& b) {
        if (a.val - b.val < 0) return a.val - b.val + mod;
        else return a.val - b.val;
    }
    friend Modular operator*(const Modular& a, const Modular& b) {
        return 1ll * a.val * b.val % mod;
    }
    friend Modular binpow(Modular a, long long n) {
        Modular res = 1;
        for (; n; n >>= 1) {
            if (n & 1) res *= a;
            a *= a;
        }
        return res;
    }
    /* ALTERNATIVE INVERSE FUNCTION USING EXTENDED EUCLIDEAN ALGORITHM
    friend void gcd(int a, int b, Modular& x, Modular& y) {
        if (a == 0) {
            x = Modular(0);
            y = Modular(1);
            return;
        }
        Modular x1, y1;
        gcd(b % a, a, x1, y1);
        x = y1 - (b / a) * x1;
        y = x1;
    }
    friend Modular inv(const Modular& a) {
        Modular x, y;
        gcd(a.val, mod, x, y);
        return x;
    }
    */
    friend Modular inv(const Modular& a) {
        return binpow(a, mod - 2);
    }
    Modular operator/(const Modular& ot) const {
        return *this * inv(ot);
    }
    Modular& operator++() {
        if (val + 1 == mod) val = 0;
        else ++val;
        return *this;
    }
    Modular operator++(int) {
        Modular tmp = *this;
        ++(*this);
        return tmp;
    }
    Modular operator+() const {
        return *this;
    }
    Modular operator-() const {
        return 0 - *this;
    }
    Modular& operator+=(const Modular& ot) {
        return *this = *this + ot;
    }
    Modular& operator-=(const Modular& ot) {
        return *this = *this - ot;
    }
    Modular& operator*=(const Modular& ot) {
        return *this = *this * ot;
    }
    Modular& operator/=(const Modular& ot) {
        return *this = *this / ot;
    }
    bool operator==(const Modular& ot) const {
        return val == ot.val;
    }
    bool operator!=(const Modular& ot) const {
        return val != ot.val;
    }
    bool operator<(const Modular& ot) const {
        return val < ot.val;
    }
    bool operator>(const Modular& ot) const {
        return val > ot.val;
    }
    explicit operator int() const {
        return val;
    }
};

template <int mod>
Modular<mod> any_to_mint(ll a) {
    a %= mod;
    return a < 0 ? a + mod : a;
}

template<int mod>
istream& operator>>(istream& istr, Modular<mod>& x) {
    return istr >> x.val;
}

template<int mod>
ostream& operator<<(ostream& ostr, const Modular<mod>& x) {
    return ostr << x.val;
}

template <int mod = 998244353, int root = 3>
class NTT {
    using Mint = Modular<mod>;
public:
    static vector<int> mult(const vector<int>& a, const vector<int>& b) {
        vector<Mint> amod(a.size());
        vector<Mint> bmod(b.size());
        for (int i = 0; i < a.size(); i++) {
            amod[i] = any_to_mint<mod>(a[i]);
        }
        for (int i = 0; i < b.size(); i++) {
            bmod[i] = any_to_mint<mod>(b[i]);
        }
        vector<Mint> resmod = mult(amod, bmod);
        vector<int> res(resmod.size());
        for (int i = 0; i < res.size(); i++) {
            res[i] = resmod[i].val;
        }
        return res;
    }
    static vector<Mint> mult(const vector<Mint>& a, const vector<Mint>& b) {
        int n = int(a.size()), m = int(b.size());
        if (!n || !m) return {};
        int lg = 0;
        while ((1 << lg) < n + m - 1) lg++;
        int z = 1 << lg;
        auto a2 = a, b2 = b;
        a2.resize(z);
        b2.resize(z);
        nft(false, a2);
        nft(false, b2);
        for (int i = 0; i < z; i++) a2[i] *= b2[i];
        nft(true, a2);
        a2.resize(n + m - 1);
        Mint iz = inv(Mint(z));
        for (int i = 0; i < n + m - 1; i++) a2[i] *= iz;
        return a2;
    }

private:
    static void nft(bool type, vector<Modular<mod>> &a) {
        int n = int(a.size()), s = 0;
        while ((1 << s) < n) s++;
        assert(1 << s == n);
        static vector<Mint> ep, iep;
        while (int(ep.size()) <= s) {
            ep.push_back(binpow(Mint(root), (mod - 1) / (1 << ep.size())));
            iep.push_back(inv(ep.back()));
        }
        vector<Mint> b(n);
        for (int i = 1; i <= s; i++) {
            int w = 1 << (s - i);
            Mint base = type ? iep[i] : ep[i], now = 1;
            for (int y = 0; y < n / 2; y += w) {
                for (int x = 0; x < w; x++) {
                    auto l = a[y << 1 | x];
                    auto r = now * a[y << 1 | x | w];
                    b[y | x] = l + r;
                    b[y | x | n >> 1] = l - r;
                }
                now *= base;
            }
            swap(a, b);
        }
    }
};

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++) {
        vector<int> p(n, 0);
        vector<int> 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 = NTT<998244353, 3>::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++) {
        vector<int> p(n, 0);
        vector<int> 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 = NTT<998244353, 3>::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();

    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
}

Compilation message

sequence.cpp: In instantiation of 'static std::vector<int> NTT<mod, root>::mult(const std::vector<int>&, const std::vector<int>&) [with int mod = 998244353; int root = 3]':
sequence.cpp:299:46:   required from here
sequence.cpp:125:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |         for (int i = 0; i < a.size(); i++) {
      |                         ~~^~~~~~~~~~
sequence.cpp:128:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |         for (int i = 0; i < b.size(); i++) {
      |                         ~~^~~~~~~~~~
sequence.cpp:133:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |         for (int i = 0; i < res.size(); i++) {
      |                         ~~^~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 500 ms 77488 KB Output is correct
2 Correct 493 ms 79036 KB Output is correct
3 Correct 496 ms 77508 KB Output is correct
4 Correct 501 ms 77676 KB Output is correct
5 Correct 487 ms 77472 KB Output is correct
6 Correct 500 ms 77492 KB Output is correct
7 Correct 499 ms 77480 KB Output is correct
8 Correct 490 ms 78976 KB Output is correct
9 Correct 496 ms 78812 KB Output is correct
10 Correct 488 ms 79040 KB Output is correct
11 Correct 489 ms 79052 KB Output is correct
12 Correct 494 ms 77500 KB Output is correct
13 Correct 490 ms 77496 KB Output is correct
14 Correct 493 ms 78820 KB Output is correct
15 Correct 490 ms 78996 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 77412 KB Output is correct
2 Correct 491 ms 78936 KB Output is correct
3 Correct 491 ms 77412 KB Output is correct
4 Correct 494 ms 77388 KB Output is correct
5 Correct 500 ms 77260 KB Output is correct
6 Correct 500 ms 77324 KB Output is correct
7 Correct 492 ms 78900 KB Output is correct
8 Correct 488 ms 77248 KB Output is correct
9 Correct 486 ms 79040 KB Output is correct
10 Correct 493 ms 79116 KB Output is correct
11 Correct 495 ms 78820 KB Output is correct
12 Correct 490 ms 78928 KB Output is correct
13 Correct 493 ms 79204 KB Output is correct
14 Correct 494 ms 77476 KB Output is correct
15 Correct 497 ms 77804 KB Output is correct
16 Correct 486 ms 79076 KB Output is correct
17 Correct 485 ms 78828 KB Output is correct
18 Correct 494 ms 77588 KB Output is correct
19 Correct 489 ms 79004 KB Output is correct
20 Correct 490 ms 79184 KB Output is correct
21 Correct 491 ms 79104 KB Output is correct
22 Correct 487 ms 78944 KB Output is correct
23 Correct 487 ms 79060 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 494 ms 78892 KB Output is correct
2 Correct 488 ms 79176 KB Output is correct
3 Correct 490 ms 79140 KB Output is correct
4 Correct 493 ms 79432 KB Output is correct
5 Correct 488 ms 79176 KB Output is correct
6 Correct 491 ms 79240 KB Output is correct
7 Correct 949 ms 80216 KB Output is correct
8 Correct 641 ms 80288 KB Output is correct
9 Correct 953 ms 80532 KB Output is correct
10 Correct 952 ms 80532 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 488 ms 77440 KB Output is correct
2 Correct 490 ms 78956 KB Output is correct
3 Correct 490 ms 77488 KB Output is correct
4 Correct 491 ms 77252 KB Output is correct
5 Correct 640 ms 79696 KB Output is correct
6 Correct 498 ms 77444 KB Output is correct
7 Correct 493 ms 77472 KB Output is correct
8 Correct 489 ms 79060 KB Output is correct
9 Correct 495 ms 77280 KB Output is correct
10 Correct 485 ms 79036 KB Output is correct
11 Correct 951 ms 80408 KB Output is correct
12 Correct 957 ms 80396 KB Output is correct
13 Correct 492 ms 78968 KB Output is correct
14 Correct 495 ms 79444 KB Output is correct
15 Correct 487 ms 78932 KB Output is correct
16 Correct 492 ms 79120 KB Output is correct
17 Correct 490 ms 77260 KB Output is correct
18 Correct 488 ms 77436 KB Output is correct
19 Correct 495 ms 78988 KB Output is correct
20 Correct 496 ms 79068 KB Output is correct
21 Correct 494 ms 77476 KB Output is correct
22 Correct 491 ms 79204 KB Output is correct
23 Correct 488 ms 78956 KB Output is correct
24 Correct 490 ms 78980 KB Output is correct
25 Correct 488 ms 79044 KB Output is correct
26 Correct 486 ms 78936 KB Output is correct
27 Correct 501 ms 79184 KB Output is correct
28 Correct 489 ms 79184 KB Output is correct
29 Correct 491 ms 79128 KB Output is correct
30 Correct 496 ms 79320 KB Output is correct
31 Correct 487 ms 78972 KB Output is correct
32 Correct 948 ms 80064 KB Output is correct
33 Correct 643 ms 79768 KB Output is correct
34 Correct 954 ms 80600 KB Output is correct
35 Correct 951 ms 80676 KB Output is correct
36 Correct 948 ms 80320 KB Output is correct
37 Correct 968 ms 80648 KB Output is correct
38 Correct 644 ms 76960 KB Output is correct
39 Correct 948 ms 80564 KB Output is correct
40 Correct 953 ms 80468 KB Output is correct