Submission #865687

#	Time	Username	Problem	Language	Result	Execution time	Memory
865687		azimanov	Sequence (BOI14_sequence)	C++17	67 / 100	993 ms	81908 KiB

sequence

#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 L = 18;
const int C = 10;
const int N = 1e5 + 10;
const int M = 1e6 + 1e5 + 10;

int cnt_suf[C][M];

ll pw10[L];
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;
}

int vec_to_mask(const vector<int>& vec) {
    int mask = 0;
    for (int i : vec) {
        mask |= (1 << i);
    }
    return mask;
}

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;
            }
        }
    }

    pw10[0] = 1;
    for (int i = 1; i < L; i++) {
        pw10[i] = pw10[i - 1] * 10;
    }

    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++) {
            if (mask == 0 && last == 0) {
                continue;
            }
            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 ? 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][len_suf]) {
                    need_suf |= (1 << c);
                }
            }
            ans = min(ans, dp[need_pref][need_suf] * n + i);
        }
    }
    return ans;
}

ll solve_same(int k) {
    for (int i = 1; i <= k - 1; i++) {
        if (b[i] != b[i + 1]) {
            return inf;
        }
    }
    for (int n = 1; n + k - 1 <= M - 1; n++) {
        if (cnt_suf[b[1]][n] >= k) {
            return n;
        }
    }
    return -1;
}

ll slow(int k) {
    for (int n = 1; n <= 1000; n++) {
        bool ok = true;
        for (int i = 1; i <= k; i++) {
            ok &= getbit(flag_true[n + i - 1], b[i]);
        }
        if (ok) {
            return n;
        }
    }
    return -1;
}

void stress() {
    mt19937 rnd;
    while (true) {
        int k = rnd() % 100 + 1;
        for (int i = 1; i <= k; i++) {
            b[i] = rnd() % C;
        }
        ll res = slow(k);
        if (res == -1) {
            continue;
        }
        ll ans = solve(k);
        if (ans == res) {
            cout << "OK" << endl;
        } else {
            cout << "WA\n";
            cout << k << "\n";
            for (int i = 1; i <= k; i++) {
                cout << b[i] << " ";
            }
            cout << "\n\n";
            cout << ans << " " << res << "\n";
            break;
        }
    }
    exit(0);
}

void gen_same(int& k, int trg_k, int trg_b) {
    k = trg_k;
    for (int i = 1; i <= k; i++) {
        b[i] = trg_b;
    }
}

void stress_same() {
    mt19937 rnd;
    while (true) {
        int k = rnd() % 1000 + 99000;
        b[1] = rnd() % C;
        for (int i = 2; i <= k; i++) {
            b[i] = b[i - 1];
        }

        ll ans = solve(k);
        ll res = solve_same(k);

        if (ans == res) {
            cout << "OK" << endl;
        } else {
            cout << "WA\n";
            cout << k << "\n";
            cout << "b[i] = " << b[1] << "\n";
            cout << "\n\n";
            cout << ans << " " << res << "\n";
            break;
        }
    }
    exit(0);
}

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

    init();

    // stress();
    // stress_same();

    // cout << dp[vec_to_mask({1, 2, 3})][vec_to_mask({9, 0, 1, 4})] << "\n";

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

    // gen_same(k, 90239, 0);

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

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

Compilation message (stderr)

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:317: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 / 9
• Subtask 2: 33 / 33
• Subtask 3: 25 / 25
• Subtask 4: 0 / 33