結果

問題 No.1354 Sambo's Treasure
コンテスト
ユーザー 🐬hec
提出日時 2021-01-17 16:12:34
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 8,269 bytes
コンパイル時間 3,781 ms
コンパイル使用メモリ 146,628 KB
実行使用メモリ 23,316 KB
最終ジャッジ日時 2024-11-29 19:28:03
合計ジャッジ時間 70,455 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 40 TLE * 21
権限があれば一括ダウンロードができます

ソースコード

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

        // cerr << "Index: " << i << endl;

        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, l + 1) rep(b, a + 1, l + 1) {
            cur[a] -= cur[b] * Combination(b, a);
        }

        // cerr << "Cur: " << endl;
        // rep(a, l + 1) {
        //     cerr << cur[a] << " ";
        // }
        // cerr << endl;

        vector<mint> nxt(l + 1, ZERO);
        rep(a, l + 1) rep(b, l + 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--;
            }
        }
    }

    // cerr << k << endl;

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

    cout << ans << endl;

    return 0;
}
0