제출 #1272398

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272398		Art	Relativnost (COCI15_relativnost)	C++20	126 / 140	4091 ms	2488 KiB

relativnost

//      - Art -
#pragma GCC optimize("O3,unroll-loops") // O2
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>

#define el              cout << '\n'

#define FOR(i, a, b)    for (int i = (a), _b = (b); i <= _b; ++i)
#define REV(i, b, a)    for (int i = (b), _a = (a); i >= _a; --i)
#define REP(i, c)       for (int i = 0, _c = (c); i < _c; ++i)

const int N = 1e5 + 7;
const int MOD = 1e4 + 7;
const int BLOCKSIZE = 578;
const int NUMBLOCK = N / BLOCKSIZE + 7;

using namespace std;

namespace IO {
    constexpr bool UNSAFE = false;
    constexpr int GLOB_BUF_SIZE = 1 << 15;
    #define CHANGE_DEFAULT_STREAMS
    static struct FastInput {
        FastInput() {
            if constexpr (UNSAFE) {
                chars_read = fread(buf, 1, BUF_SIZE, in);
                buf_pos = 0;
                buf[0] = (chars_read == 0 ? -1 : buf[0]);
            }
        }
        static constexpr int BUF_SIZE = GLOB_BUF_SIZE;
        char buf[BUF_SIZE];
        size_t chars_read = 0;
        size_t buf_pos = 0;
        FILE *in = stdin;
        char cur = 0;
        inline char get_char() {
            if constexpr (!UNSAFE) {
                if (buf_pos >= chars_read) {
                    chars_read = fread(buf, 1, BUF_SIZE, in);
                    buf_pos = 0;
                    buf[0] = (chars_read == 0 ? -1 : buf[0]);
                }
            }
            return cur = buf[buf_pos++];
        }
        template<typename T> inline FastInput *tie(T) { return this; }
        inline void sync_with_stdio(bool) {}
        inline explicit operator bool() { return cur != -1; }
        inline static bool is_blank(char c) { return c <= ' '; }
        inline bool skip_blanks() {
            while (is_blank(cur) && cur != -1) get_char();
            return cur != -1;
        }
        inline FastInput &operator>>(char &c) {
            skip_blanks();
            c = cur;
            get_char();
            return *this;
        }
        inline FastInput &operator>>(std::string &s) {
            if (skip_blanks()) {
                s.clear();
                do {
                    s += cur;
                } while (!is_blank(get_char()));
            }
            return *this;
        }
        template<typename T> inline FastInput &read_integer(T &n) {
            // unsafe, doesn't check that characters are actually digits
            n = 0;
            if (skip_blanks()) {
                int sign = +1;
                if (cur == '-') {
                    sign = -1;
                    get_char();
                }
                do {
                    n += n + (n << 3) + cur - '0';
                } while (!is_blank(get_char()));
                n *= sign;
            }
            return *this;
        }
        template<typename T>
        inline typename std::
            enable_if<std::is_integral<T>::value, FastInput &>::type
            operator>>(T &n) {
            return read_integer(n);
        }
    #if !defined(_WIN32) || defined(_WIN64)
        inline FastInput &operator>>(__int128 &n) { return read_integer(n); }
    #endif
        template<typename T>
        inline typename std::
            enable_if<std::is_floating_point<T>::value, FastInput &>::type
            operator>>(T &n) {
            // not sure if really fast, for compatibility only
            n = 0;
            if (skip_blanks()) {
                std::string s;
                (*this) >> s;
                sscanf(s.c_str(), "%lf", &n);
            }
            return *this;
        }
    } fast_input;
    #define cin IO::fast_input
    static struct FastOutput {
        static constexpr int BUF_SIZE = GLOB_BUF_SIZE;
        char buf[BUF_SIZE];
        size_t buf_pos = 0;
        static constexpr int TMP_SIZE = GLOB_BUF_SIZE;
        char tmp[TMP_SIZE];
        FILE *out = stdout;
        inline void put_char(char c) {
            buf[buf_pos++] = c;
            if (buf_pos == BUF_SIZE) {
                fwrite(buf, 1, buf_pos, out);
                buf_pos = 0;
            }
        }
        ~FastOutput() { fwrite(buf, 1, buf_pos, out); }
        inline FastOutput &operator<<(char c) {
            put_char(c);
            return *this;
        }
        inline FastOutput &operator<<(const char *s) {
            while (*s) put_char(*s++);
            return *this;
        }
        inline FastOutput &operator<<(const std::string &s) {
            for (auto x : s) put_char(x);
            return *this;
        }
        template<typename T> inline char *integer_to_string(T n) {
            // beware of TMP_SIZE
            char *p = tmp + TMP_SIZE - 1;
            if (n == 0)
                *--p = '0';
            else {
                bool is_negative = false;
                if (n < 0) {
                    is_negative = true;
                    n = -n;
                }
                while (n > 0) {
                    *--p = (char)('0' + n % 10);
                    n /= 10;
                }
                if (is_negative) *--p = '-';
            }
            return p;
        }
        template<typename T>
        inline typename std::enable_if<std::is_integral<T>::value, char *>::type
        stringify(T n) {
            return integer_to_string(n);
        }
    #if !defined(_WIN32) || defined(_WIN64)
        inline char *stringify(__int128 n) { return integer_to_string(n); }
    #endif
        template<typename T>
        inline typename std::
            enable_if<std::is_floating_point<T>::value, char *>::type
            stringify(T n) {
            sprintf(tmp, "%.17f", n);
            return tmp;
        }
        template<typename T> inline FastOutput &operator<<(const T &n) {
            auto p = stringify(n);
            for (; *p != 0; p++) put_char(*p);
            return *this;
        }
    } fast_output;
    #define cout IO::fast_output
}

int a[N], b[N];

namespace naive {
    int dp[N][22];

    void solve(int n, int k) {
        int q;
        cin >> q;
        while (q--) {
            int id, na, nb;
            cin >> id >> na >> nb;
            na %= MOD;
            nb %= MOD;
            a[id] = na;
            b[id] = nb;

            dp[0][0] = 1;
            FOR (i, 1, n) REP (j, k) {
                dp[i][j] = dp[i - 1][j] * b[i] % MOD;
                if (j > 0) {
                    dp[i][j] = (dp[i][j] + dp[i - 1][j - 1] * a[i]) % MOD;
                }
            }

            int tot = 1;
            FOR (i, 1, n) {
                tot = (a[i] + b[i]) * tot % MOD;
            }
            REP (i, k) {
                tot = (tot - dp[n][i] + MOD) % MOD;
            }
            cout << tot, el;
        }
    }
}

int block[N];
int dp[NUMBLOCK][22];
int pre[NUMBLOCK][22];

int main() {

//    #define name "art"
//    if (fopen(name".inp", "r")) {
//        freopen(name".inp", "r", stdin);
//        freopen(name".out", "w", stdout);
//    }

//    ios_base::sync_with_stdio(false);
//    cin.tie(0); cout.tie(0);

    auto inverse = [&](int a) -> int {
        int b = MOD - 2, res = 1;
        while (b) {
            if (b & 1) {
                res = res * a % MOD;
            }
            a = a * a % MOD;
            b >>= 1;
        }
        return res;
    };

    int n, k;
    cin >> n >> k;
    FOR (i, 1, n) {
        cin >> a[i];
        a[i] %= MOD;
    }
    FOR (i, 1, n) {
        cin >> b[i];
        b[i] %= MOD;
    }

    if (n <= 5000) {
        naive::solve(n, k);
        return 0;
    }

    int tot = 1;
    REP (i, n) {
        block[i] = i / BLOCKSIZE;
        a[i] = a[i + 1];
        b[i] = b[i + 1];
        tot = (a[i] + b[i]) * tot % MOD;
    }

    FOR (x, 0, block[n - 1]) {
        int l = x * BLOCKSIZE;
        int r = min(n, l + BLOCKSIZE) - 1;
        dp[x][0] = b[l];
        dp[x][1] = a[l];
        FOR (i, l + 1, r) REV (j, k - 1, 0) {
            dp[x][j] = (dp[x][j] * b[i]) % MOD;
            if (j > 0) {
                dp[x][j] = (dp[x][j] + dp[x][j - 1] * a[i]) % MOD;
            }
        }
        if (x > 0) {
            REP (j, k) REP (o, j + 1) {
                pre[x][j] = (pre[x][j] + pre[x - 1][o] * dp[x][j - o]) % MOD;
            }
        }
        else {
            REP (j, k) {
                pre[x][j] = dp[x][j];
            }
        }
    }

    int q;
    cin >> q;
    while (q--) {
        int id, na, nb;
        cin >> id >> na >> nb;
        na %= MOD;
        nb %= MOD;
        --id;
        tot = tot * inverse(a[id] + b[id]) % MOD;
        tot = tot * (na + nb) % MOD;
        a[id] = na;
        b[id] = nb;

        int x = block[id];
        int l = x * BLOCKSIZE;
        int r = min(n, l + BLOCKSIZE) - 1;
        memset(dp[x], 0, sizeof dp[x]);
        dp[x][0] = b[l];
        dp[x][1] = a[l];
        FOR (i, l + 1, r) {
            REV (j, k - 1, 0) {
                dp[x][j] = dp[x][j] * b[i] % MOD;
                if (j > 0) {
                    dp[x][j] = (dp[x][j] + dp[x][j - 1] * a[i]) % MOD;
                }
            }
        }

        int res = tot;
        for (; x <= block[n - 1]; ++x) {
            if (x > 0) {
                memset(pre[x], 0, sizeof pre[x]);
                REP (j, k) {
                    REP (o, j + 1) {
                        pre[x][j] = (pre[x][j] + pre[x - 1][o] * dp[x][j - o]) % MOD;
                    }
                }
            }
            else {
                REP (j, k) {
                    pre[x][j] = dp[x][j];
                }
            }
        }

        REP (j, k) {
            res = (res - pre[block[n - 1]][j] + MOD) % MOD;
        }
        cout << res, el;
    }

//    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";

    return 0;
}

• Subtask 1: 126 / 140