답안 #865795

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
865795 2023-10-24T16:11:28 Z azimanov 수열 (BOI14_sequence) C++17
42 / 100
724 ms 98144 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 = 2e5 + 10;
const int M = 1e6 + 1e5 + 10;

int cnt_suf[C][M];

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

int rig_true[C][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;
            }
        }
    }

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

    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 = 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[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] = rig_true[c][i] = r[i + k - 1];
        }
    }
    {
        vector<int> p(n, 0);
        vector<int> q(k, 0);
        for (int i = 0; i < n; i++) {
            int new_flag = flag[i];
            if (i < 9'999) {
                flag[i] |= (1 << 0);
            }
            p[i] = getbit(new_flag, 0);
        }
        for (int i = 1; i <= k; i++) {
            q[k - i] = b[i] == 0;
        }
        auto r = NTT<998244353, 3>::mult(p, q);
        for (int i = 0; i < n; i++) {
            lef[0][i] = r[i];
            rig[0][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]++;
    }
}

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

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

ll dp_slow[(1 << C)][(1 << C)];

int ll_to_mask(ll x) {
    int mask = 0;
    while (x > 0) {
        mask |= (1 << (x % 10));
        x /= 10;
    }
    return mask;
}

void stress_dp() {
    for (int i = 0; i < (1 << C); i++) {
        for (int j = 0; j < (1 << C); j++) {
            dp_slow[i][j] = inf;
        }
    }
    for (int i = 1; i <= 1e7; i++) {
        int x = ll_to_mask(i);
        int y = ll_to_mask(i + 1);
        dp_slow[x][y] = min(dp_slow[x][y], ll(i));
    }
    for (int i = 0; i < (1 << C); i++) {
        for (int j = 0; j < (1 << C); j++) {
            if (dp_slow[i][j] != inf && dp[i][j] != dp_slow[i][j]) {
                cout << "WA\n";
                cout << i << " " << j << "\n";
                cout << dp[i][j] << " " << dp_slow[i][j] << "\n";
                exit(0);
            }
        }
    }
    cout << "OK" << endl;
    exit(0);
}

bool check(int k, ll ans) {
    for (int i = 1; i <= k; i++) {
        if (!getbit(ll_to_mask(ans + i - 1), b[i])) {
            return false;
        }
    }
    return true;
}

void stress_check_big() {
    mt19937 rnd;
    while (true) {
        int k = rnd() % 1000 + 90000;
        for (int i = 1; i <= k; i++) {
            b[i] = rnd() % C;
        }
        ll ans = solve(k);
        if (check(k, ans)) {
            cout << "OK " << k << " " << ans << endl;
        } else {
            cout << "WA\n";
            cout << k << "\n";
            cout << "b ?\n\n";
            cout << ans << "\n";
            break;
        }
    }
    exit(0);
}

void stress_big() {
    mt19937 rnd;
    while (true) {
        int k = rnd() % 100 + 90000;
        ll res = rnd() % 123123123 + 1;
        for (int i = 1; i <= k; i++) {
            int mask = ll_to_mask(res + i - 1);
            vector<int> vec;
            for (int c = 0; c < C; c++) {
                if (getbit(mask, c)) {
                    vec.push_back(c);
                }
            }
            b[i] = vec[rnd() % vec.size()];
        }

        ll ans = solve(k);
        bool ok = check(k, ans);
        if (ok && ans <= res) {
            cout << "OK " << k << " " << ans << " " << res << endl;
        } else {
            cout << "WA\n";
            cout << k << "\n";
            cout << "b ?\n\n";
            cout << ans << " " << res << "\n";
            cout << (ok ? "good" : "bad") << "\n";
            break;
        }
    }
    exit(0);
}

void gen_big(int& k, int trg_k, ll trg_ans) {
    k = trg_k;
    mt19937 rnd;
    for (int i = 1; i <= k; i++) {
        int mask = ll_to_mask(trg_ans + i - 1);
        vector<int> vec;
        for (int c = 0; c < C; c++) {
            if (getbit(mask, c)) {
                vec.push_back(c);
            }
        }
        b[i] = vec[rnd() % vec.size()];
        bool ok = false;
        for (char ch : to_string(trg_ans + i - 1)) {
            if ((ch - '0') == b[i]) {
                ok = true;
            }
        }
        assert(ok);
    }
    assert(check(k, trg_ans));
}

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

    init();

    // stress();
    // stress_same();
    // stress_dp();
    // stress_check_big();
    // stress_big();

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

    // gen_same(k, 90239, 0);

//    int trg_k = 90012;
//    ll trg_ans = 89376811;
//    gen_big(k, trg_k, trg_ans);

    cout << solve(k) << "\n";
    // cout << solve_same(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:296: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++) {
      |                         ~~^~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 393 ms 95096 KB Output is correct
2 Correct 390 ms 96936 KB Output is correct
3 Correct 389 ms 95144 KB Output is correct
4 Correct 395 ms 95036 KB Output is correct
5 Correct 389 ms 95012 KB Output is correct
6 Correct 398 ms 95044 KB Output is correct
7 Correct 390 ms 95028 KB Output is correct
8 Correct 390 ms 96768 KB Output is correct
9 Correct 386 ms 96940 KB Output is correct
10 Correct 394 ms 96620 KB Output is correct
11 Correct 385 ms 96744 KB Output is correct
12 Correct 393 ms 95100 KB Output is correct
13 Correct 394 ms 95012 KB Output is correct
14 Correct 390 ms 96936 KB Output is correct
15 Correct 392 ms 96692 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 396 ms 95200 KB Output is correct
2 Correct 388 ms 96540 KB Output is correct
3 Correct 395 ms 95164 KB Output is correct
4 Correct 395 ms 95136 KB Output is correct
5 Correct 394 ms 95008 KB Output is correct
6 Correct 390 ms 95196 KB Output is correct
7 Correct 390 ms 96848 KB Output is correct
8 Correct 389 ms 95096 KB Output is correct
9 Correct 386 ms 96656 KB Output is correct
10 Correct 388 ms 96608 KB Output is correct
11 Correct 385 ms 96600 KB Output is correct
12 Correct 385 ms 96564 KB Output is correct
13 Correct 388 ms 96592 KB Output is correct
14 Correct 387 ms 95108 KB Output is correct
15 Correct 387 ms 95092 KB Output is correct
16 Correct 403 ms 96696 KB Output is correct
17 Correct 389 ms 96688 KB Output is correct
18 Correct 396 ms 95368 KB Output is correct
19 Correct 389 ms 96656 KB Output is correct
20 Correct 390 ms 96784 KB Output is correct
21 Correct 385 ms 96624 KB Output is correct
22 Correct 389 ms 96700 KB Output is correct
23 Correct 385 ms 96656 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 389 ms 96624 KB Output is correct
2 Correct 387 ms 96848 KB Output is correct
3 Correct 393 ms 96820 KB Output is correct
4 Incorrect 391 ms 96908 KB Output isn't correct
5 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 389 ms 95180 KB Output is correct
2 Correct 386 ms 96564 KB Output is correct
3 Correct 390 ms 95008 KB Output is correct
4 Correct 388 ms 95040 KB Output is correct
5 Correct 392 ms 97380 KB Output is correct
6 Correct 387 ms 95136 KB Output is correct
7 Correct 393 ms 95016 KB Output is correct
8 Correct 388 ms 96652 KB Output is correct
9 Correct 389 ms 95136 KB Output is correct
10 Correct 388 ms 96892 KB Output is correct
11 Incorrect 724 ms 98144 KB Output isn't correct
12 Halted 0 ms 0 KB -