#603449 (C++17) No.1354 Sambo's Treasure

提出ソース

結果

問題	No.1354 Sambo's Treasure
ユーザー	KoD
提出日時	2021-01-15 18:53:16
言語	C++17 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	121 ms / 2,000 ms
コード長	5,322 bytes
コンパイル時間	2,589 ms
コンパイル使用メモリ	221,828 KB
実行使用メモリ	12,788 KB
最終ジャッジ日時	2023-08-22 08:05:28
合計ジャッジ時間	8,138 ms
ジャッジサーバーID （参考情報）	judge14 / judge12

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,376 KB
testcase_01	AC	2 ms 4,380 KB
testcase_02	AC	1 ms 4,376 KB
testcase_03	AC	2 ms 4,380 KB
testcase_04	AC	1 ms 4,384 KB
testcase_05	AC	2 ms 4,380 KB
testcase_06	AC	2 ms 4,376 KB
testcase_07	AC	2 ms 4,376 KB
testcase_08	AC	2 ms 4,376 KB
testcase_09	AC	2 ms 4,376 KB
testcase_10	AC	1 ms 4,380 KB
testcase_11	AC	1 ms 4,380 KB
testcase_12	AC	1 ms 4,376 KB
testcase_13	AC	1 ms 4,380 KB
testcase_14	AC	1 ms 4,380 KB
testcase_15	AC	2 ms 4,380 KB
testcase_16	AC	1 ms 4,376 KB
testcase_17	AC	2 ms 4,380 KB
testcase_18	AC	1 ms 4,380 KB
testcase_19	AC	2 ms 4,384 KB
testcase_20	AC	2 ms 4,376 KB
testcase_21	AC	2 ms 4,376 KB
testcase_22	AC	2 ms 4,380 KB
testcase_23	AC	117 ms 12,508 KB
testcase_24	AC	121 ms 12,564 KB
testcase_25	AC	115 ms 12,444 KB
testcase_26	AC	115 ms 12,552 KB
testcase_27	AC	116 ms 12,404 KB
testcase_28	AC	117 ms 12,504 KB
testcase_29	AC	120 ms 12,472 KB
testcase_30	AC	117 ms 12,404 KB
testcase_31	AC	117 ms 12,748 KB
testcase_32	AC	116 ms 12,608 KB
testcase_33	AC	116 ms 12,568 KB
testcase_34	AC	118 ms 12,556 KB
testcase_35	AC	119 ms 12,564 KB
testcase_36	AC	120 ms 12,512 KB
testcase_37	AC	118 ms 12,652 KB
testcase_38	AC	116 ms 12,584 KB
testcase_39	AC	117 ms 12,788 KB
testcase_40	AC	119 ms 12,552 KB
testcase_41	AC	117 ms 12,520 KB
testcase_42	AC	117 ms 12,588 KB
testcase_43	AC	9 ms 6,468 KB
testcase_44	AC	10 ms 6,232 KB
testcase_45	AC	10 ms 6,324 KB
testcase_46	AC	9 ms 6,420 KB
testcase_47	AC	10 ms 6,416 KB
testcase_48	AC	10 ms 6,184 KB
testcase_49	AC	9 ms 6,468 KB
testcase_50	AC	10 ms 6,292 KB
testcase_51	AC	10 ms 6,316 KB
testcase_52	AC	10 ms 6,444 KB
testcase_53	AC	10 ms 6,288 KB
testcase_54	AC	10 ms 6,408 KB
testcase_55	AC	9 ms 6,388 KB
testcase_56	AC	10 ms 6,456 KB
testcase_57	AC	10 ms 6,488 KB
testcase_58	AC	10 ms 6,348 KB
testcase_59	AC	10 ms 6,456 KB
testcase_60	AC	10 ms 6,420 KB
testcase_61	AC	9 ms 6,468 KB
testcase_62	AC	10 ms 6,204 KB
testcase_63	AC	116 ms 12,564 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>

template <class T>
using Vec = std::vector<T>;

constexpr unsigned MOD = 998244353;

struct Fp {
    unsigned val;
    explicit Fp(const unsigned val = 0): val(val) { }

    void operator += (const Fp other) {
        val += other.val;
        if (val >= MOD) {
            val -= MOD;
        }
    }
    void operator -= (const Fp other) {
        val += MOD - other.val;
        if (val >= MOD) {
            val -= MOD;
        }
    }
    void operator *= (const Fp other) {
        val = (unsigned long long) val * other.val % MOD;
    }

    Fp operator + (const Fp other) const {
        Fp ret(*this);
        ret += other;
        return ret;
    }
    Fp operator - (const Fp other) const {
        Fp ret(*this);
        ret -= other;
        return ret;
    }
    Fp operator * (const Fp other) const {
        Fp ret(*this);
        ret *= other;
        return ret;
    }

    Fp inv() const {
        Fp ret(1), mult(*this);
        unsigned exp = MOD - 2;
        while (exp > 0) {
            if (exp & 1) {
                ret *= mult;
            }
            exp >>= 1;
            mult *= mult;
        }
        return ret;
    }
};

struct FpUtil {
    Vec<Fp> fact;
    Vec<Fp> inv_fact;
    explicit FpUtil(const unsigned size): fact(size + 1), inv_fact(size + 1) { 
        fact[0] = Fp(1);
        for (int i = 1; i <= (int) size; ++i) {
            fact[i] = fact[i - 1] * Fp(i);
        }
        inv_fact[size] = fact[size].inv();
        for (int i = (int) size; i >= 1; --i) {
            inv_fact[i - 1] = inv_fact[i] * Fp(i);
        }
    }

    Fp binom(const unsigned a, const unsigned b) const {
        return fact[a + b] * inv_fact[a] * inv_fact[b];
    }
};

int main() {
    int N, M, L, K;
    std::cin >> N >> M >> L >> K;
    assert(1 <= N && N <= 200000);
    assert(0 <= M && M <= std::min(N - 1, 100000));
    assert(0 <= L && L <= std::min((long long) (N + 1) * (N + 1), (long long) 100));
    assert(0 <= K && K <= 100000);
    Vec<std::pair<int, int>> Pts;
    Pts.reserve(2 + M);
    Pts.emplace_back(0, 0);
    for (int i = 0; i < M; ++i) {
        int x, y;
        std::cin >> x >> y;
        Pts.emplace_back(x, y);
    }
    Pts.emplace_back(N, N);
    for (int i = 0; i + 1 < (int) Pts.size(); ++i) {
        assert(Pts[i].first < Pts[i + 1].first);
        assert(Pts[i].second < Pts[i + 1].second);
    }
    std::set<std::pair<int, int>> set;
    for (int i = 0; i < L; ++i) {
        int x, y;
        std::cin >> x >> y;
        assert(0 <= x && x <= N);
        assert(0 <= y && y <= N);
        set.emplace(x, y);
    }
    assert((int) set.size() == L);
    Vec<Vec<std::pair<int, int>>> Tig(Pts.size());
    for (int i = 0; i + 1 < (int) Pts.size(); ++i) {
        Tig[i + 1].push_back(Pts[i]);
    }
    Vec<bool> inevitable(Pts.size());
    for (const auto [x, y]: set) {
        bool inside = true;
        for (int i = 0; i < (int) Pts.size(); ++i) {
            if (x == Pts[i].first && y == Pts[i].second) {
                inevitable[i] = true;
                inside = false;
                break;
            }
        }
        if (!inside) {
            continue;
        }
        for (int i = 1; i < (int) Pts.size(); ++i) {
            if (Pts[i - 1].first <= x && x <= Pts[i].first && Pts[i - 1].second <= y && y <= Pts[i].second) {
                Tig[i].emplace_back(x, y);
                break;
            }
        }
    }    
    for (int i = 1; i < (int) Pts.size(); ++i) {
        Tig[i].push_back(Pts[i]);
    }
    Vec<Fp> dp(L + 1);
    dp[inevitable[0]] = Fp(1);
    FpUtil util(2 * N);
    for (int i = 1; i < (int) Pts.size(); ++i) {
        const auto &vec = Tig[i];
        const int size = (int) vec.size();
        Vec<Vec<Fp>> path(size, Vec<Fp>(size));
        for (int j = 0; j < size; ++j) {
            for (int k = j + 1; k < size; ++k) {
                if (vec[k].second < vec[j].second) {
                    continue;
                }
                path[j][k] = util.binom(vec[k].first - vec[j].first, vec[k].second - vec[j].second);
                for (int l = j + 1; l < k; ++l) {
                    if (vec[l].second >= vec[j].second && vec[k].second >= vec[l].second) {
                        path[j][k] -= path[j][l] * util.binom(vec[k].first - vec[l].first, vec[k].second - vec[l].second);
                    }
                }
            }
        }
        Vec<Vec<Fp>> calc(size - 2, Vec<Fp>(L + 1));
        for (int j = 0; j < size - 2; ++j) {
            for (int k = 0; k < L; ++k) {
                calc[j][k + 1] += dp[k] * path[0][j + 1];
            }
        }
        for (int j = 0; j < size - 2; ++j) {
            for (int k = j + 1; k < size - 2; ++k) {
                for (int l = 0; l < L; ++l) {
                    calc[k][l + 1] += calc[j][l] * path[j + 1][k + 1];
                }
            }
        }
        Vec<Fp> next(L + 1);
        for (int k = 0; k + inevitable[i] <= L; ++k) {
            next[k + inevitable[i]] += dp[k] * path[0][size - 1];
            for (int j = 0; j < size - 2; ++j) {
                next[k + inevitable[i]] += calc[j][k] * path[j + 1][size - 1];
            }
        }
        dp = std::move(next);
    }
    std::cout << std::accumulate(dp.begin(), dp.begin() + std::min(L, K) + 1, Fp(0)).val << '\n';
}

yukicoder

結果

テストケース

ソースコード