oj.uz

답안 #865601

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
865601 2023-10-24T11:58:15 Z azimanov 수열 (BOI14_sequence) C++17
42 / 100
 297 ms 18256 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];
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));
        }
    }
}

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

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

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

    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);
                }
            }
            if (need == 0) {
                if (i == 0) {
                    ans = min(ans, ll(n));
                } else {
                    ans = min(ans, ll(i));
                }
            } else {
                if (need == 1) {
                    need = 3;
                }
                ll x = mask_to_ll(need);
                ans = min(ans, x * n + i);
            }
        } else {

        }
    }
    return ans;
}

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() % 10 + 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);
}

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

    init();

    // stress();

    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:235: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

# 결과 실행 시간 메모리 Grader output
1 Correct 138 ms 17536 KB Output is correct
2 Correct 139 ms 17500 KB Output is correct
3 Correct 139 ms 17572 KB Output is correct
4 Correct 142 ms 17520 KB Output is correct
5 Correct 139 ms 17624 KB Output is correct
6 Correct 140 ms 17532 KB Output is correct
7 Correct 138 ms 17436 KB Output is correct
8 Correct 144 ms 17588 KB Output is correct
9 Correct 138 ms 17536 KB Output is correct
10 Correct 139 ms 17604 KB Output is correct
11 Correct 138 ms 17576 KB Output is correct
12 Correct 138 ms 17572 KB Output is correct
13 Correct 140 ms 17404 KB Output is correct
14 Correct 139 ms 17620 KB Output is correct
15 Correct 144 ms 17600 KB Output is correct

Subtask #2
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 140 ms 17564 KB Output is correct
2 Correct 138 ms 17568 KB Output is correct
3 Correct 138 ms 17576 KB Output is correct
4 Correct 138 ms 17396 KB Output is correct
5 Correct 139 ms 17504 KB Output is correct
6 Correct 140 ms 17492 KB Output is correct
7 Correct 138 ms 17612 KB Output is correct
8 Correct 139 ms 17404 KB Output is correct
9 Correct 150 ms 17612 KB Output is correct
10 Correct 138 ms 17540 KB Output is correct
11 Correct 139 ms 17608 KB Output is correct
12 Correct 138 ms 17604 KB Output is correct
13 Correct 139 ms 17532 KB Output is correct
14 Correct 138 ms 17604 KB Output is correct
15 Correct 145 ms 17664 KB Output is correct
16 Correct 138 ms 17616 KB Output is correct
17 Correct 141 ms 17612 KB Output is correct
18 Correct 138 ms 17408 KB Output is correct
19 Correct 138 ms 17568 KB Output is correct
20 Correct 138 ms 17568 KB Output is correct
21 Correct 139 ms 17408 KB Output is correct
22 Correct 139 ms 17484 KB Output is correct
23 Correct 140 ms 17612 KB Output is correct

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 138 ms 17460 KB Output is correct
2 Correct 139 ms 17712 KB Output is correct
3 Incorrect 146 ms 18256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 140 ms 17592 KB Output is correct
2 Correct 138 ms 17596 KB Output is correct
3 Correct 140 ms 17600 KB Output is correct
4 Correct 143 ms 17684 KB Output is correct
5 Correct 286 ms 17264 KB Output is correct
6 Correct 141 ms 17392 KB Output is correct
7 Correct 150 ms 17504 KB Output is correct
8 Correct 139 ms 17464 KB Output is correct
9 Correct 147 ms 17532 KB Output is correct
10 Correct 138 ms 17440 KB Output is correct
11 Incorrect 297 ms 18028 KB Output isn't correct
12 Halted 0 ms 0 KB -