結果
問題 | No.1596 Distance Sum in 2D Plane |
ユーザー | qLethon |
提出日時 | 2021-07-09 22:16:30 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 339 ms / 2,000 ms |
コード長 | 4,712 bytes |
コンパイル時間 | 2,191 ms |
コンパイル使用メモリ | 197,620 KB |
最終ジャッジ日時 | 2025-01-22 22:01:00 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
#include <bits/stdc++.h> using namespace std; template <std::uint_fast64_t Modulus> class modint { using u64 = std::uint_fast64_t; u64 a; public: template <class INT> constexpr modint(const INT x = 0) noexcept : a(x >= 0 ? x % Modulus : x % int_fast64_t(Modulus) + Modulus) {} constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {} constexpr u64 &value() noexcept { return a; } constexpr const u64 &value() const noexcept { return a; } constexpr modint operator+(const modint rhs) const noexcept { return modint(*this) += rhs; } constexpr modint operator-(const modint rhs) const noexcept { return modint(*this) -= rhs; } constexpr modint operator*(const modint rhs) const noexcept { return modint(*this) *= rhs; } constexpr modint operator/(const modint rhs) const noexcept { return modint(*this) /= rhs; } constexpr modint &operator+=(const modint rhs) noexcept { a += rhs.a; if (a >= Modulus) { a -= Modulus; } return *this; } constexpr modint &operator-=(const modint rhs) noexcept { if (a < rhs.a) { a += Modulus; } a -= rhs.a; return *this; } constexpr modint &operator*=(const modint rhs) noexcept { a = a * rhs.a % Modulus; return *this; } constexpr modint &operator/=(modint rhs) noexcept { u64 exp = Modulus - 2; while (exp) { if (exp % 2) { *this *= rhs; } rhs *= rhs; exp /= 2; } return *this; } constexpr bool operator<(const modint& rhs) const noexcept {return this->a < rhs.a;} constexpr bool operator>(const modint& rhs) const noexcept {return rhs < *this;} constexpr bool operator<=(const modint& rhs) const noexcept {return !(*this > rhs);} constexpr bool operator>=(const modint& rhs) const noexcept {return !(*this < rhs);} constexpr bool operator==(const modint& rhs) const noexcept {return this->a == rhs.a;} constexpr bool operator!=(const modint& rhs) const noexcept {return !(*this == rhs);} constexpr modint& operator++() noexcept { *this += modint(1); return *this; } constexpr modint operator++(int) noexcept { modint tmp(*this); ++(*this); return tmp; } constexpr modint& operator--() noexcept { *this -= modint(1); return *this; } constexpr modint operator--(int) noexcept { modint tmp(*this); --(*this); return tmp; } constexpr modint operator-() const noexcept { return modint(0) - *this; } template <std::uint_fast64_t M> friend constexpr std::ostream& operator<<(std::ostream& os, const modint<M>& rhs) noexcept { os << rhs.a; return os; } template <std::uint_fast64_t M> friend constexpr std::istream& operator>>(std::istream& is, modint<M>& rhs) noexcept { int64_t tmp; is >> tmp; rhs = modint(tmp); return is; } constexpr modint pow(const u64 k) const noexcept { if (k == 0) return 1; if (k % 2 == 0){ modint res = pow(k / 2); return res * res; } return pow(k - 1) * modint(*this); } template <typename T> operator const T (){return a;} }; const constexpr int64_t p = 1e9 + 7; using mint = modint<p>; template<class Modint> class Binomial{ vector<Modint> fact(uint64_t n){ vector<Modint> f(n + 1); f[0] = 1; for (uint64_t i = 0; i < n; i++) f[i + 1] = Modint(i + 1) * f[i]; return f; } vector<Modint> invfact(uint64_t n){ vector<Modint> inv(n + 1); inv[n] = Modint(1) / f[n]; for (uint64_t i = n; i > 0; i--) inv[i - 1] = inv[i] * i; return inv; } public: vector<Modint> f, invf; Binomial(uint64_t n){ f = fact(n); invf = invfact(n); } Modint binomial(int64_t a, int64_t b){ if (a < b) return 0; if (a < 0 or b < 0) return 0; return f[a] * invf[b] * invf[a - b]; } }; int main(){ int n; cin >> n; Binomial<mint> binom(2 * n); mint s = binom.binomial(2 * n, n) * 2 * n; int m; cin >> m; for (int i = 0; i < m; i++){ int t, h, w; cin >> t >> h >> w; if (t == 1) s -= binom.binomial(h + w, h) * binom.binomial(n - (h + 1) + n - w, n - w); else s -= binom.binomial(h + w, h) * binom.binomial(n - h + n - (w + 1), n - h); } cout << s << endl; }