結果

問題 No.1354 Sambo's Treasure
ユーザー 🐬hec🐬hec
提出日時 2021-01-17 16:14:24
言語 C++17(clang)
(17.0.6 + boost 1.83.0)
結果
AC  
実行時間 489 ms / 2,000 ms
コード長 8,065 bytes
コンパイル時間 1,963 ms
コンパイル使用メモリ 146,624 KB
実行使用メモリ 12,172 KB
最終ジャッジ日時 2024-12-16 03:59:57
合計ジャッジ時間 14,368 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 31 ms
11,124 KB
testcase_01 AC 31 ms
11,224 KB
testcase_02 AC 31 ms
11,072 KB
testcase_03 AC 33 ms
11,300 KB
testcase_04 AC 33 ms
11,152 KB
testcase_05 AC 34 ms
11,140 KB
testcase_06 AC 32 ms
11,232 KB
testcase_07 AC 33 ms
11,148 KB
testcase_08 AC 31 ms
11,176 KB
testcase_09 AC 31 ms
11,088 KB
testcase_10 AC 32 ms
11,076 KB
testcase_11 AC 31 ms
11,136 KB
testcase_12 AC 33 ms
11,084 KB
testcase_13 AC 33 ms
11,152 KB
testcase_14 AC 33 ms
11,252 KB
testcase_15 AC 32 ms
11,096 KB
testcase_16 AC 31 ms
11,080 KB
testcase_17 AC 31 ms
11,252 KB
testcase_18 AC 31 ms
11,104 KB
testcase_19 AC 32 ms
11,132 KB
testcase_20 AC 32 ms
11,188 KB
testcase_21 AC 32 ms
11,240 KB
testcase_22 AC 32 ms
11,132 KB
testcase_23 AC 433 ms
12,020 KB
testcase_24 AC 475 ms
12,112 KB
testcase_25 AC 446 ms
12,100 KB
testcase_26 AC 447 ms
12,160 KB
testcase_27 AC 437 ms
12,116 KB
testcase_28 AC 458 ms
12,172 KB
testcase_29 AC 481 ms
12,144 KB
testcase_30 AC 429 ms
12,040 KB
testcase_31 AC 466 ms
12,068 KB
testcase_32 AC 433 ms
11,980 KB
testcase_33 AC 489 ms
12,068 KB
testcase_34 AC 446 ms
12,064 KB
testcase_35 AC 457 ms
11,992 KB
testcase_36 AC 477 ms
12,100 KB
testcase_37 AC 452 ms
12,056 KB
testcase_38 AC 466 ms
11,968 KB
testcase_39 AC 468 ms
12,028 KB
testcase_40 AC 455 ms
12,124 KB
testcase_41 AC 456 ms
12,092 KB
testcase_42 AC 470 ms
12,004 KB
testcase_43 AC 36 ms
11,180 KB
testcase_44 AC 36 ms
11,068 KB
testcase_45 AC 35 ms
11,148 KB
testcase_46 AC 33 ms
11,204 KB
testcase_47 AC 33 ms
11,216 KB
testcase_48 AC 33 ms
11,144 KB
testcase_49 AC 33 ms
11,068 KB
testcase_50 AC 32 ms
11,092 KB
testcase_51 AC 32 ms
11,128 KB
testcase_52 AC 33 ms
11,200 KB
testcase_53 AC 32 ms
11,140 KB
testcase_54 AC 33 ms
11,188 KB
testcase_55 AC 33 ms
11,140 KB
testcase_56 AC 33 ms
11,144 KB
testcase_57 AC 34 ms
11,192 KB
testcase_58 AC 34 ms
11,084 KB
testcase_59 AC 32 ms
11,096 KB
testcase_60 AC 33 ms
11,232 KB
testcase_61 AC 34 ms
11,124 KB
testcase_62 AC 33 ms
11,084 KB
testcase_63 AC 479 ms
12,084 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0