oj.uz

Submission #865806

# Submission time Handle Problem Language Result Execution time Memory
865806 2023-10-24T16:50:40 Z azimanov Sequence (BOI14_sequence) C++17
100 / 100
 929 ms 37692 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;

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() {
    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:277: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 462 ms 34448 KB Output is correct
2 Correct 458 ms 36020 KB Output is correct
3 Correct 462 ms 34684 KB Output is correct
4 Correct 456 ms 34244 KB Output is correct
5 Correct 462 ms 34352 KB Output is correct
6 Correct 469 ms 34272 KB Output is correct
7 Correct 463 ms 34308 KB Output is correct
8 Correct 460 ms 36184 KB Output is correct
9 Correct 454 ms 35976 KB Output is correct
10 Correct 454 ms 36348 KB Output is correct
11 Correct 452 ms 35996 KB Output is correct
12 Correct 458 ms 34244 KB Output is correct
13 Correct 461 ms 34516 KB Output is correct
14 Correct 452 ms 35808 KB Output is correct
15 Correct 462 ms 36236 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 465 ms 34712 KB Output is correct
2 Correct 452 ms 35992 KB Output is correct
3 Correct 461 ms 34412 KB Output is correct
4 Correct 467 ms 34380 KB Output is correct
5 Correct 472 ms 34400 KB Output is correct
6 Correct 464 ms 34472 KB Output is correct
7 Correct 453 ms 35812 KB Output is correct
8 Correct 464 ms 34360 KB Output is correct
9 Correct 454 ms 35772 KB Output is correct
10 Correct 463 ms 35996 KB Output is correct
11 Correct 459 ms 35848 KB Output is correct
12 Correct 452 ms 35904 KB Output is correct
13 Correct 460 ms 35940 KB Output is correct
14 Correct 459 ms 34240 KB Output is correct
15 Correct 459 ms 34548 KB Output is correct
16 Correct 468 ms 35860 KB Output is correct
17 Correct 464 ms 35772 KB Output is correct
18 Correct 466 ms 34640 KB Output is correct
19 Correct 457 ms 35824 KB Output is correct
20 Correct 458 ms 35980 KB Output is correct
21 Correct 465 ms 36176 KB Output is correct
22 Correct 461 ms 36004 KB Output is correct
23 Correct 462 ms 35852 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 456 ms 35940 KB Output is correct
2 Correct 456 ms 36152 KB Output is correct
3 Correct 459 ms 36168 KB Output is correct
4 Correct 455 ms 36040 KB Output is correct
5 Correct 459 ms 36244 KB Output is correct
6 Correct 459 ms 35996 KB Output is correct
7 Correct 908 ms 36884 KB Output is correct
8 Correct 605 ms 36776 KB Output is correct
9 Correct 925 ms 37368 KB Output is correct
10 Correct 929 ms 37356 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 459 ms 34308 KB Output is correct
2 Correct 461 ms 36108 KB Output is correct
3 Correct 457 ms 34252 KB Output is correct
4 Correct 459 ms 34344 KB Output is correct
5 Correct 605 ms 36800 KB Output is correct
6 Correct 456 ms 34432 KB Output is correct
7 Correct 464 ms 34380 KB Output is correct
8 Correct 452 ms 35780 KB Output is correct
9 Correct 459 ms 34272 KB Output is correct
10 Correct 452 ms 35892 KB Output is correct
11 Correct 918 ms 37264 KB Output is correct
12 Correct 923 ms 37560 KB Output is correct
13 Correct 454 ms 35924 KB Output is correct
14 Correct 459 ms 36544 KB Output is correct
15 Correct 454 ms 35984 KB Output is correct
16 Correct 453 ms 35996 KB Output is correct
17 Correct 462 ms 34636 KB Output is correct
18 Correct 458 ms 34204 KB Output is correct
19 Correct 460 ms 36000 KB Output is correct
20 Correct 452 ms 35772 KB Output is correct
21 Correct 455 ms 34272 KB Output is correct
22 Correct 458 ms 36060 KB Output is correct
23 Correct 455 ms 36028 KB Output is correct
24 Correct 460 ms 35772 KB Output is correct
25 Correct 453 ms 35876 KB Output is correct
26 Correct 464 ms 36032 KB Output is correct
27 Correct 463 ms 36260 KB Output is correct
28 Correct 454 ms 36132 KB Output is correct
29 Correct 464 ms 36088 KB Output is correct
30 Correct 463 ms 36252 KB Output is correct
31 Correct 455 ms 36036 KB Output is correct
32 Correct 910 ms 37004 KB Output is correct
33 Correct 611 ms 36620 KB Output is correct
34 Correct 920 ms 37680 KB Output is correct
35 Correct 918 ms 37504 KB Output is correct
36 Correct 920 ms 37116 KB Output is correct
37 Correct 917 ms 37488 KB Output is correct
38 Correct 623 ms 34212 KB Output is correct
39 Correct 918 ms 37672 KB Output is correct
40 Correct 924 ms 37692 KB Output is correct