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

提出ソース

結果

問題	No.1354 Sambo's Treasure
ユーザー	🐬hec
提出日時	2021-01-17 16:14:24
言語	C++17(clang) (17.0.6 + boost 1.83.0)
結果	AC
実行時間	468 ms / 2,000 ms
コード長	8,065 bytes
コンパイル時間	1,629 ms
コンパイル使用メモリ	112,028 KB
実行使用メモリ	12,216 KB
最終ジャッジ日時	2023-08-22 08:19:05
合計ジャッジ時間	14,475 ms
ジャッジサーバーID （参考情報）	judge13 / judge15

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	35 ms 10,920 KB
testcase_01	AC	34 ms 11,216 KB
testcase_02	AC	35 ms 11,340 KB
testcase_03	AC	35 ms 11,252 KB
testcase_04	AC	35 ms 11,244 KB
testcase_05	AC	34 ms 11,224 KB
testcase_06	AC	34 ms 11,180 KB
testcase_07	AC	35 ms 10,972 KB
testcase_08	AC	35 ms 11,088 KB
testcase_09	AC	35 ms 11,076 KB
testcase_10	AC	35 ms 11,264 KB
testcase_11	AC	34 ms 11,228 KB
testcase_12	AC	35 ms 11,228 KB
testcase_13	AC	35 ms 11,228 KB
testcase_14	AC	35 ms 11,040 KB
testcase_15	AC	35 ms 11,264 KB
testcase_16	AC	35 ms 11,184 KB
testcase_17	AC	35 ms 11,148 KB
testcase_18	AC	35 ms 11,052 KB
testcase_19	AC	35 ms 11,248 KB
testcase_20	AC	35 ms 10,912 KB
testcase_21	AC	35 ms 11,340 KB
testcase_22	AC	35 ms 11,036 KB
testcase_23	AC	423 ms 11,984 KB
testcase_24	AC	435 ms 12,124 KB
testcase_25	AC	416 ms 12,028 KB
testcase_26	AC	431 ms 12,016 KB
testcase_27	AC	432 ms 12,076 KB
testcase_28	AC	429 ms 12,216 KB
testcase_29	AC	444 ms 12,072 KB
testcase_30	AC	436 ms 12,060 KB
testcase_31	AC	445 ms 12,136 KB
testcase_32	AC	438 ms 12,164 KB
testcase_33	AC	422 ms 12,020 KB
testcase_34	AC	444 ms 11,948 KB
testcase_35	AC	452 ms 12,048 KB
testcase_36	AC	468 ms 12,020 KB
testcase_37	AC	455 ms 12,068 KB
testcase_38	AC	440 ms 12,016 KB
testcase_39	AC	441 ms 12,044 KB
testcase_40	AC	463 ms 12,028 KB
testcase_41	AC	457 ms 12,096 KB
testcase_42	AC	459 ms 12,148 KB
testcase_43	AC	36 ms 11,076 KB
testcase_44	AC	36 ms 11,244 KB
testcase_45	AC	36 ms 11,276 KB
testcase_46	AC	37 ms 11,072 KB
testcase_47	AC	36 ms 11,044 KB
testcase_48	AC	36 ms 11,172 KB
testcase_49	AC	36 ms 11,216 KB
testcase_50	AC	36 ms 11,252 KB
testcase_51	AC	36 ms 11,036 KB
testcase_52	AC	36 ms 11,252 KB
testcase_53	AC	36 ms 10,960 KB
testcase_54	AC	36 ms 11,264 KB
testcase_55	AC	36 ms 11,076 KB
testcase_56	AC	36 ms 11,000 KB
testcase_57	AC	36 ms 11,024 KB
testcase_58	AC	36 ms 11,172 KB
testcase_59	AC	37 ms 11,036 KB
testcase_60	AC	36 ms 10,936 KB
testcase_61	AC	37 ms 10,988 KB
testcase_62	AC	37 ms 11,012 KB
testcase_63	AC	437 ms 12,056 KB

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

ソースコード

raw source code

#include <algorithm>
#include <bitset>
#include <cmath>
#include <complex>
#include <cstdio>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <sys/types.h>
#include <unistd.h>
#include <vector>

#pragma region macros
#define _overload(_1, _2, _3, name, ...) name
#define _rep(i, n) _range(i, 0, n)
#define _range(i, a, b) for (int i = int(a); i < int(b); ++i)
#define rep(...) _overload(__VA_ARGS__, _range, _rep, )(__VA_ARGS__)
#define _rrep(i, n) _rrange(i, n, 0)
#define _rrange(i, a, b) for (int i = int(a) - 1; i >= int(b); --i)
#define rrep(...) _overload(__VA_ARGS__, _rrange, _rrep, )(__VA_ARGS__)
#pragma endregion macros

using namespace std;

template <class T> bool chmax(T &a, const T &b) {
    return (a < b) ? (a = b, 1) : 0;
}
template <class T> bool chmin(T &a, const T &b) {
    return (b < a) ? (a = b, 1) : 0;
}

using ll    = long long;
using R     = long double;
const R EPS = 1e-9L;  // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R &r) {
    return (r > EPS) - (r < -EPS);
}
inline R sq(R x) {
    return sqrt(max(x, 0.0L));
}

const pid_t pid = getpid();
// Problem Specific Parameter:

class ModInt
{
  public:
    static unsigned MOD;
    ModInt(): x(0) {}
    ModInt(signed y): x(y >= 0 ? y % MOD : MOD - (-y) % MOD) {}
    ModInt(signed long long y): x(y >= 0 ? y % MOD : MOD - (-y) % MOD) {}


    // Arithmetic Oprators
    ModInt &operator+=(ModInt that) {
        if ((x += that.x) >= MOD)
            x -= MOD;
        return *this;
    }
    ModInt &operator-=(ModInt that) {
        if ((x += MOD - that.x) >= MOD)
            x -= MOD;
        return *this;
    }
    ModInt &operator*=(ModInt that) {
        x = 1LL * x * that.x % MOD;
        return *this;
    }
    ModInt &operator/=(ModInt that) {
        return *this *= ModInt(get<1>(extgcd(that.x, int(MOD))));
    }
    ModInt &operator%=(ModInt that) {
        x %= that.x;
        return *this;
    }

    ModInt &operator+=(const int that) {
        return *this += ModInt(that);
    }
    ModInt &operator-=(const int that) {
        return *this -= ModInt(that);
    }
    ModInt &operator*=(const int that) {
        return *this *= ModInt(that);
    }
    ModInt &operator/=(const int that) {
        return *this /= ModInt(that);
    }
    ModInt &operator%=(const int that) {
        return *this %= ModInt(that);
    }

    // Comparators
    bool operator<(ModInt that) {
        return x < that.x;
    }
    bool operator>(ModInt that) {
        return x > that.x;
    }
    bool operator<=(ModInt that) {
        return x <= that.x;
    }
    bool operator>=(ModInt that) {
        return x >= that.x;
    }
    bool operator!=(ModInt that) {
        return x != that.x;
    }
    bool operator==(ModInt that) {
        return x == that.x;
    }

    // Utilities
    unsigned getval() const {
        return x;
    }
    ModInt operator+(ModInt that) const {
        return ModInt(*this) += that;
    }
    ModInt operator-(ModInt that) const {
        return ModInt(*this) -= that;
    }
    ModInt operator*(ModInt that) const {
        return ModInt(*this) *= that;
    }
    ModInt operator/(ModInt that) const {
        return ModInt(*this) /= that;
    }
    ModInt operator%(ModInt that) const {
        return ModInt(*this) %= that;
    }
    ModInt operator+(const int that) const {
        return ModInt(*this) += that;
    }
    ModInt operator-(const int that) const {
        return ModInt(*this) -= that;
    }
    ModInt operator*(const int that) const {
        return ModInt(*this) *= that;
    }
    ModInt operator/(const int that) const {
        return ModInt(*this) /= that;
    }
    ModInt operator%(const int that) const {
        return ModInt(*this) %= that;
    }
    ModInt operator=(const int that) {
        return *this = ModInt(that);
    }
    friend istream &operator>>(istream &is, ModInt &that) {
        ll tmp;
        is >> tmp;
        that = ModInt(tmp);
        return is;
    }
    friend ostream &operator<<(ostream &os, const ModInt &that) {
        return os << that.x;
    }

    ModInt power(ll n) const {
        ll b = 1LL, a = x;
        while (n) {
            if (n & 1)
                b = b * a % MOD;
            a = a * a % MOD;
            n >>= 1;
        }
        return ModInt(b);
    }

  private:
    unsigned x;

    inline tuple<int, int, int> extgcd(int a, int b) {
        if (b == 0)
            return make_tuple(a, 1, 0);
        tuple<int, int, int> ret = extgcd(b, a % b);
        swap(get<1>(ret), get<2>(ret));
        get<2>(ret) -= a / b * get<1>(ret);
        return ret;
    }
};

unsigned ModInt::MOD = 998244353;
using mint           = ModInt;
const mint ZERO      = mint(0);
const mint ONE       = mint(1);
const mint TWO       = mint(2);

vector<mint> Fact, InvFact;
void makeFact(int n) {
    Fact                     = vector<mint>(n + 1);
    Fact[0]                  = mint(1);
    rep(i, 1, n + 1) Fact[i] = mint(i) * Fact[i - 1];

    InvFact               = vector<mint>(n + 1);
    InvFact[n]            = Fact[n].power(ModInt::MOD - 2);
    rrep(i, n) InvFact[i] = mint(i + 1) * InvFact[i + 1];
}

mint Factorial(int n) {
    return Fact[n];
}

mint InverseFactorial(int n) {
    return InvFact[n];
}
mint Permutation(int n, int k) {
    return (n < 0 or k < 0 or n - k < 0) ? ZERO : Fact[n] * InvFact[n - k];
}
mint Combination(int n, int k) {
    return (n < 0 or k < 0 or n - k < 0)
               ? ZERO
               : Fact[n] * InvFact[k] * InvFact[n - k];
}


int main(void) {
    int n, m, l, k;
    cin >> n >> m >> l >> k;

    vector<int> xm = {0}, ym = {0};
    rep(i, m) {
        int xv, yv;
        cin >> xv >> yv;
        xm.push_back(xv);
        ym.push_back(yv);
    }
    xm.push_back(n);
    ym.push_back(n);


    vector<int> xt(l), yt(l);
    rep(i, l) {
        cin >> xt[i] >> yt[i];
    }

    makeFact(1000000);

    vector<mint> dp(l + 1, ZERO);
    dp[0] = ONE;

    rep(i, m + 1) {
        const int sx = xm[i], sy = ym[i];
        const int tx = xm[i + 1], ty = ym[i + 1];


        using pii       = pair<int, int>;
        vector<pii> ary = {pii(sx, sy), pii(tx, ty)};

        rep(j, l) {
            if (sx <= xt[j] and xt[j] <= tx and sy <= yt[j] and yt[j] <= ty) {
                if (!(sx == xt[j] and sy == yt[j])
                    and !(tx == xt[j] and ty == yt[j])) {
                    ary.push_back(pii(xt[j], yt[j]));
                }
            }
        }

        sort(begin(ary), end(ary));
        const int all = ary.size();

        mint dp2[110][110];
        mint coef[110][110];


        rep(a, all) rep(b, all) {
            dp2[a][b]  = ZERO;
            coef[a][b] = ZERO;
        }

        dp2[0][0] = ONE;

        rep(a, all) rep(b, a + 1, all) {
            const int dx = ary[b].first - ary[a].first;
            const int dy = ary[b].second - ary[a].second;
            coef[a][b]   = Combination(dx + dy, dx);
        }


        rep(a, all) rep(b, all) {
            // dp2[a][b]
            if (dp2[a][b] == ZERO) {
                continue;
            }

            rep(c, a + 1, all) {
                dp2[c][b + 1] += coef[a][c] * dp2[a][b];
            }
        }

        vector<mint> cur(l + 1, ZERO);

        rrep(a, all - 1) {
            cur[a] = dp2[all - 1][a + 1];
        }

        rrep(a, all - 1) rep(b, a + 1, all - 1) {
            cur[a] -= cur[b] * Combination(b, a);
        }

        vector<mint> nxt(l + 1, ZERO);
        rep(a, l + 1) rep(b, all - 1) {
            if (a + b <= l) {
                nxt[a + b] += dp[a] * cur[b];
            }
        }

        rep(a, l + 1) {
            dp[a] = nxt[a];
        }
    }

    rep(i, m + 1) {
        const int sx = xm[i], sy = ym[i];
        rep(j, l) {
            if (sx == xt[j] and sy == yt[j]) {
                k--;
            }
        }
    }

    mint ans = ZERO;
    rep(i, l + 1) {
        if (i <= k) {
            ans += dp[i];
        }
    }

    cout << ans << endl;

    return 0;
}

yukicoder

結果

テストケース

ソースコード