結果
問題 | No.907 Continuous Kadomatu |
ユーザー | btk |
提出日時 | 2019-10-12 00:15:11 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 919 ms / 2,000 ms |
コード長 | 24,237 bytes |
コンパイル時間 | 2,447 ms |
コンパイル使用メモリ | 221,000 KB |
実行使用メモリ | 28,600 KB |
最終ジャッジ日時 | 2024-11-25 20:52:54 |
合計ジャッジ時間 | 5,921 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 9 ms
27,776 KB |
testcase_01 | AC | 9 ms
27,904 KB |
testcase_02 | AC | 10 ms
27,904 KB |
testcase_03 | AC | 9 ms
27,904 KB |
testcase_04 | AC | 9 ms
27,952 KB |
testcase_05 | AC | 17 ms
27,824 KB |
testcase_06 | AC | 10 ms
27,776 KB |
testcase_07 | AC | 12 ms
27,904 KB |
testcase_08 | AC | 16 ms
27,904 KB |
testcase_09 | AC | 13 ms
27,960 KB |
testcase_10 | AC | 21 ms
27,904 KB |
testcase_11 | AC | 25 ms
27,904 KB |
testcase_12 | AC | 39 ms
27,956 KB |
testcase_13 | AC | 41 ms
27,904 KB |
testcase_14 | AC | 44 ms
27,776 KB |
testcase_15 | AC | 43 ms
27,904 KB |
testcase_16 | AC | 45 ms
27,904 KB |
testcase_17 | AC | 47 ms
27,904 KB |
testcase_18 | AC | 43 ms
27,776 KB |
testcase_19 | AC | 47 ms
27,904 KB |
testcase_20 | AC | 18 ms
28,160 KB |
testcase_21 | AC | 9 ms
27,824 KB |
testcase_22 | AC | 9 ms
27,828 KB |
testcase_23 | AC | 919 ms
28,416 KB |
testcase_24 | AC | 917 ms
28,600 KB |
testcase_25 | AC | 8 ms
27,904 KB |
testcase_26 | AC | 9 ms
27,828 KB |
testcase_27 | AC | 9 ms
27,904 KB |
testcase_28 | AC | 9 ms
27,828 KB |
testcase_29 | AC | 9 ms
28,032 KB |
ソースコード
// https://yukicoder.me/problems/no/907 #define CIN_ONLY #define DECIMAL_DIGITS 10 #define STATIC_MOD 1e9 + 7 #ifdef BTK /*<head>*/ # include "Template.hpp" # include "num/ModInt.hpp" /*</head>*/ #else /*<body>*/ /* #region auto includes */ /* #region stl */ /*<stl>*/ # include <bits/stdc++.h> # include <sys/types.h> # include <unistd.h> using namespace std; /*</stl>*/ /* #endregion */ /* #region template/IncludeSTL.hpp*/ /** * @file IncludeSTL.hpp * @author btk * @brief 標準ライブラリをincludeするだけ * @version 0.1 * @date 2019-07-21 * @todo 何故か2回includeされる(展開scriptに * @copyright Copyright (c) 2019 * */ /* #endregion */ /* #region template/Macro.hpp*/ /** * @file Macro.hpp * @author btk * @brief マクロとか,LLとか * @version 0.1 * @date 2019-07-13 * * @copyright Copyright (c) 2019 * */ //! LL using LL = long long; /** * @def DEBUG * @brief デバッグ用のif文 提出時はif(0)で実行されない */ /*</head>*/ # ifdef BTK # define DEBUG if (1) # else # ifdef CIN_ONLY # define FAST_IO # endif # define DEBUG if (0) # endif /** * @def ALL(v) * @brief * ALLマクロ */ # define ALL(v) (v).begin(), (v).end() /** * @def REC(ret, ...) * @brief * 再帰ラムダをするためのマクロ */ # define REC(ret, ...) std::function<ret(__VA_ARGS__)> /** * @def VAR_NAME(var) * @brief 変数名を取得する */ # define VAR_NAME(var) # var /** * @brief * rangeで生まれる使わない変数を消す用(警告消し) */ template <typename T> inline T& unused_var(T& v) { return v; } /* #endregion */ /* #region template/IO.hpp*/ /** * @file IO.hpp * @author btk * @brief cin高速化とか,出力の小数桁固定とか * @version 0.1 * @date 2019-07-13 * * @copyright Copyright (c) 2019 */ /** * @brief 入出力の設定を行うための構造体 */ struct cww { /** * @brief Construct a new cww::cww object * @details * CIN_ONLYを定義すると,submit時にcinとscanfの同期を切る設定が走る * DECIMAL_DIGITSを定義すると,doubleの出力時指定した桁数分小数部を吐くようになる */ cww() { # ifdef FAST_IO ios::sync_with_stdio(false); cin.tie(0); # endif # ifdef DECIMAL_DIGITS cout << fixed; cout << setprecision(DECIMAL_DIGITS); # endif } }; //! 入出力設定構造体を実体化 cww star; /** * @brief * vectorに直接cin流すためのやつ * @tparam T * @param is * @param v * @return istream& */ template <typename T> std::istream& operator>>(std::istream& is, std::vector<T>& v) { for (auto& it : v) is >> it; return is; } /* #endregion */ /* #region template/Loop.hpp*/ /** * @file Loop.hpp * @author btk * @brief rangeとかループ系のクラス * @version 0.1 * @date 2019-07-13 * * @copyright Copyright (c) 2019 * */ /** * @brief * rangeを逆向きに操作したいとき用 * @details * ループの範囲は[bg,ed)なので注意 * @see range */ class reverse_range { private: struct I { int x; int operator*() { return x - 1; } bool operator!=(I& lhs) { return x > lhs.x; } void operator++() { --x; } }; I i, n; public: /** * @brief Construct a new reverse range object * * @param n */ reverse_range(int n) : i({0}), n({n}) {} /** * @brief Construct a new reverse range object * * @param i * @param n */ reverse_range(int i, int n) : i({i}), n({n}) {} /** * @brief * begin iterator * @return I& */ I& begin() { return n; } /** * @brief * end iterator * @return I& */ I& end() { return i; } }; /** * @brief * python みたいな range-based for を実現 * @details * ループの範囲は[bg,ed)なので注意 * !つけると逆向きにループが回る (reverse_range) * 空間計算量はO(1) * 使わない変数ができて警告が出がちなので,unused_varとかを使って警告消しするとよい */ class range { private: struct I { int x; int operator*() { return x; } bool operator!=(I& lhs) { return x < lhs.x; } void operator++() { ++x; } }; I i, n; public: /** * @brief Construct a new range object * * @param n */ range(int n) : i({0}), n({n}) {} /** * @brief Construct a new range object * * @param i * @param n */ range(int i, int n) : i({i}), n({n}) {} /** * @brief * begin iterator * @return I& */ I& begin() { return i; } /** * @brief * end iterator * @return I& */ I& end() { return n; } /** * @brief * 逆向きに参照するrange(reverse_rangeを取得できるs) * @return reverse_range */ reverse_range operator!() { return reverse_range(*i, *n); } }; /* #endregion */ /* #region template/MinMaxOperation.hpp*/ /** * @file MinMaxOperation.hpp * @author btk * @brief 最大値とか最小値を求める * @version 0.1 * @date 2019-07-04 * * @copyright Copyright (c) 2019 * */ /** * @brief 2項の最小値求める * * @tparam T */ template <typename T> struct min_op { /** * @brief 本体 * * @param l * @param r * @return T */ static T exec(const T l, const T r) { return l < r ? l : r; } }; /** * @brief 2項の最大値求める * * @tparam T */ template <typename T> struct max_op { /** * @brief 本体 * * @param l * @param r * @return T */ static T exec(const T l, const T r) { return l > r ? l : r; } }; /** * @brief テンプレート再帰の末尾 * * @tparam F 二項演算 * @tparam T * @param v * @return T */ template <typename F, typename T> inline T multi_op(T&& v) { return v; } /** * @brief 複数項における演算の結果を返す * * @tparam F * @tparam T * @tparam Ts * @param head * @param tail * @return T */ template <typename F, typename T, typename... Ts> inline T multi_op(const T head, Ts&&... tail) { return F::exec(head, multi_op<F>(tail...)); } /** * @brief 複数項の最小値 * @see multi_op * @tparam T * @tparam Ts * @param head * @param tail * @return T */ template <typename T, typename... Ts> inline T multi_min(T&& head, Ts&&... tail) { return multi_op<min_op<T>>(head, tail...); } /** * @brief 複数項の最大値 * @see multi_op * @tparam T * @tparam Ts * @param head * @param tail * @return T */ template <typename T, typename... Ts> inline T multi_max(T&& head, Ts&&... tail) { return multi_op<max_op<T>>(head, tail...); } /** * @brief * 先頭の値をFで参照する関数に基づいて変更できたらする * @tparam F * @tparam T * @tparam Ts * @param target * @param candidates * @return true * @return false */ template <typename F, typename T, typename... Ts> inline bool ch_op(T& target, Ts&&... candidates) { const T old = target; target = multi_op<F>(target, candidates...); return old != target; } /** * @brief change min * @tparam T 型 * @param target 変更する値 * @param candidates * @return 更新があればtrue */ template <typename T, typename... Ts> inline bool chmin(T& target, Ts&&... candidates) { return ch_op<min_op<T>>(target, candidates...); } /** * @brief chminのmax版 * @see chmin * @tparam T 型 * @param target 変更する値 * @param candidates * @return 更新があればtrue */ template <typename T, typename... Ts> inline bool chmax(T& target, Ts&&... candidates) { return ch_op<max_op<T>>(target, candidates...); } /* #endregion */ /* #region template/Random.hpp*/ /** * @file Random.hpp * @author btk * @brief 乱数生成系 * @version 0.1 * @date 2019-07-13 * @copyright Copyright (c) 2019 */ //! 乱数のシード値をプロセスIDとして取得 const pid_t pid = getpid(); /** * @brief XorShift32の実装 */ class XorShift32 { private: //! XorShiftの現在の値 unsigned value; /** * @brief XorShift32のアルゴリズムに基づいて value を更新 */ inline void update() { value = value ^ (value << 13); value = value ^ (value >> 17); value = value ^ (value << 5); } /** * @brief 値を更新し,更新前の値を返却 * @return unsigned 呼び出し時の value を用いる */ inline unsigned get() { unsigned v = value; update(); return v; } public: /** * @brief [0, 2^bit) の範囲の乱数値を取り出す * @tparam デフォルトは31 * @return int */ template <int bit = 31> inline int next_int() { return (int)(get() >> (32 - bit)); } /** * @brief [-2^bit,2^bit)の範囲の乱数値を取り出す * @tparam デフォルトは31 * @return int */ template <int bit = 31> inline int next_signed() { unsigned v = get(); return (int)((v >> (31 - bit)) - (1 << (bit))); } /** * @brief next_int呼び出し時の最大値を取得 * @tparam 31 * @return int */ template <int bit = 31> inline int range_max() { return (int)((1u << bit) - 1); }; /** * @brief Construct a new XorShift32 object * @param seed * @details 初期シードをvalueとするXorShift32のインスタンスを生成 */ XorShift32(const unsigned seed) { value = seed; update(); } /** * @brief Construct a new XorShift 32 object * @details 初期シードをプロセスIDとするXorShift32のインスタンスを生成 */ XorShift32() : XorShift32(pid) {} }; /* #endregion */ /* #region Template.hpp*/ /** * @file Template.hpp * @brief 競技プログラミング用テンプレート * @author btk15049 * @date 2019/05/02 */ /* #endregion */ /* #region num/ModInt.hpp*/ # include <utility> /** * @file ModInt.hpp * @brief mod構造体 * @author btk15049 * @date 2019/03/08 * @details * \todo verifyが足りない * verify: CSA12E,RUPC day3 F */ //! [WARNING!] mod が入力で与えられる場合はconstexprを外す # ifdef STATIC_MOD constexpr int mod = STATIC_MOD; # else int mod; # endif /** * @brief mod構造体 * @details * 整数をラップして,常に保持されているデータがmodされた状態になるよう管理. */ class ModInt { private: //! 中身 int x; public: /** * @brief ゲッター * @details 出力時などは "cout << *ret << endl;"のようにやるとよい. */ long long operator*() const { return x; } /** * @brief デフォルトコンストラクタ.0で初期化される. */ ModInt() { x = 0; } /** * @brief intからのコンストラクタ * @param[in] y 設定したい値 * @details * modをとらないので高速.ただしmodより大きい値や負の数を入れると事故るので注意. */ ModInt(const int y) { x = y; } /** * @brief long longからのコンストラクタ * @param[in] y 設定したい値 * @details 毎回modを取るので低速. */ ModInt(const long long y) { x = (int)((mod + y % mod) % mod); } /** * @brief ModIntからの代入演算子 * @param[in] o 設定したい値 * @details 高速 */ ModInt(const ModInt& o) { this->x = *o; } /** * @brief 整数から高速にModIntを作りたいときに使う * @param[in] x 設定したい値 * @details xが[0,mod)であることが保証されてないと正しく動かない. */ static inline ModInt raw(const long long x) { // assert(x<mod); return ModInt((int)x); } /** * @brief 整数から安全にModIntを作りたいときに使う * @param[in] x 設定したい値 * @details mod2回取るから遅い.負数でもOK. */ static inline ModInt get(const long long x) { return ModInt(x); } /** * @brief intからの代入演算子 * @param[in] o 設定したい値 * @details * modをとらないので高速.ただしmodより大きい値や負の数を入れると事故るので注意. */ ModInt& operator=(const int o) { this->x = o >= mod ? o - mod : o; return *this; } /** * @brief long longからの代入演算子 * @param[in] o 設定したい値 * @details mod2回取るから遅い.負数でもOK. */ ModInt& operator=(const long long o) { this->x = (int)((mod + o % mod) % mod); return *this; } /** * @brief ModIntからの代入演算子 * @param[in] o 設定したい値 * @details 高速 */ ModInt& operator=(const ModInt o) { this->x = *o; return *this; } }; /** * @param[in] l ModInt * @param[in] r ModInt * @details if文使って少し高速化. */ inline ModInt add(const ModInt l, const ModInt r) { const long long x = *l + *r; return ModInt::raw(x >= mod ? x - mod : x); } /** * @param[in] l ModInt * @param[in] r ModInt. */ inline ModInt mul(const ModInt l, const ModInt r) { return ModInt::raw(*l * *r % mod); } /** * @brief a^x %modを求める * @param[in] a ModInt * @param[in] x long long. */ inline ModInt pow(ModInt a, long long x) { ModInt ret = ModInt::raw(1); while (x) { if (x & 1) { ret = mul(ret, a); } a = mul(a, a); x >>= 1; } return ret; } /** * @brief x^-1 %modを求める * @param[in] x ModInt. * @details * 内部ではユークリッドの拡張互助法を使っている. * O(log(mod)) */ inline ModInt inv(const ModInt x) { long long a = *x, b = mod, u = 1, v = 0; while (b) { long long t = a / b; std::swap(a -= t * b, b); std::swap(u -= t * v, v); } return ModInt::get(u); } /** * @brief 負数を求める単項演算子 * @param[in] x ModInt */ inline ModInt operator-(const ModInt x) { return add(mod, -*x); } /** * @param[in] l ModInt * @param[in] r ModInt */ inline ModInt operator+(const ModInt l, const ModInt r) { return add(l, r); } /** * @param[in] l ModInt * @param[in] r ModInt */ inline ModInt operator*(const ModInt l, const ModInt r) { return mul(l, r); } /** * @param[in] l ModInt * @param[in] r ModInt */ inline ModInt operator-(const ModInt l, const ModInt r) { return add(l, -r); } /** * @param[in] l ModInt * @param[in] r int * @details * 右辺は定数を想定しているのでmodをとらないrawを使ってModIntに変換している.ただしmodより大きい値や負の数を入れると事故るので注意. */ inline ModInt operator+(const ModInt l, const int r) { return add(l, ModInt::raw(r)); } /** * @param[in] l ModInt * @param[in] r int */ inline ModInt operator+(const ModInt l, const long long r) { return add(l, ModInt::get(r)); } /** * @param[in] l ModInt * @param[in] r int * @details * 右辺は定数を想定しているのでmodをとらないrawを使ってModIntに変換している.ただしmodより大きい値や負の数を入れると事故るので注意. */ inline ModInt operator*(const ModInt l, const int r) { return mul(l, ModInt::raw(r)); } /** * @param[in] l ModInt * @param[in] r int */ inline ModInt operator*(const ModInt l, const long long r) { return mul(l, ModInt::get(r)); } /** * @param[in] l ModInt * @param[in] r int * @details * 右辺は定数を想定しているのでmodをとらないrawを使ってModIntに変換している.ただしmodより大きい値や負の数を入れると事故るので注意. */ inline ModInt operator-(const ModInt l, const int r) { return add(l, ModInt::raw(mod - r)); } /** * @param[in] l ModInt * @param[in] r int */ inline ModInt operator-(const ModInt l, const long long r) { return add(l, -ModInt::get(r)); } /** * @param[in] l ModInt * @param[in] r int * @details * 右辺は定数を想定しているのでmodをとらないrawを使ってModIntに変換している.ただしmodより大きい値や負の数を入れると事故るので注意. */ inline ModInt operator/(const ModInt l, const int r) { return mul(l, inv(ModInt::raw(r))); } /** * @param[in] l ModInt * @param[in] r int */ inline ModInt operator/(const ModInt l, const long long r) { return mul(l, inv(ModInt::get(r))); } /** * @param[in] l ModInt * @param[in] r long long * @details * pow(l,r)を呼び出すだけなのでpowを参照のこと. 計算量はO(log mod) */ inline ModInt operator^(const ModInt l, const long long r) { return pow(l, r); } /** * @brief * +=の実装、各operator+を呼ぶだけ * @tparam T * @param l ModInt * @param r 足すやつ * @return ModInt& */ template <typename T> ModInt& operator+=(ModInt& l, T r) { l = l + r; return l; } /** * @brief * -=の実装、各operator-を呼ぶだけ * @tparam T * @param l ModInt * @param r 引くやつ * @return ModInt& */ template <typename T> ModInt& operator-=(ModInt& l, T r) { l = l - r; return l; } /** * @brief * *=の実装、各operator*を呼ぶだけ * @tparam T * @param l ModInt * @param r かけるやつ * @return ModInt& */ template <typename T> ModInt& operator*=(ModInt& l, T r) { l = l * r; return l; } /** * @namespace factorial * @brief 順列数関連の関数のまとめ * @details * - combination * - permutation * - multiChoose */ namespace factorial { //! 順列数を格納する配列のサイズ constexpr int size = # ifdef FACTORIAL_SIZE FACTORIAL_SIZE; # else 3123456; # endif //! 前計算ができているかどうかのフラグ bool is_build = false; //! 順列数を格納する配列 ModInt factorial[size]; //! (順列数)^-1を格納する配列 ModInt inverse_factorial[size]; /** * @brief 順列数の前計算 * @details * 順列数と,その逆元を[0,size)まで求める. * 計算量は,O(size + log(mod)) */ void build() { is_build = true; factorial[0] = 1; for (int i = 1; i < size; i++) { factorial[i] = factorial[i - 1] * i; } inverse_factorial[size - 1] = inv(factorial[size - 1]); for (int i = size - 1; i >= 1; i--) { inverse_factorial[i - 1] = inverse_factorial[i] * i; } } /** * @brief nPkを求める * @details * 前計算がしてあれば O(1).前計算してない場合は is_build * を読み取って前計算をする. */ inline ModInt permutation(int n, int k) { if (k < 0 || k > n) return ModInt::raw(0); if (!is_build) build(); return factorial[n] * inverse_factorial[n - k]; } /** * @brief nCkを求める * @details * 前計算がしてあれば O(1).前計算してない場合は is_build * を読み取って前計算をする. */ inline ModInt combination(int n, int k) { if (k < 0 || k > n) return ModInt::raw(0); if (!is_build) build(); return factorial[n] * inverse_factorial[k] * inverse_factorial[n - k]; } /** * @brief 重複組合せ * @param n 何種類のものを * @param r いくつ並べるか * @return ModInt nHr */ ModInt multiChoose(int n, int r) { if (n == 0 && r == 0) return ModInt::raw(1); return combination(n + r - 1, r); } /** * @brief 上限付き重複組合せ * @details * 包除原理を用いて,lim個以上の品物が1,2,...,i種類の場合を足したり引いたりしていく * 計算量は O(min(n, r / lim)) * @param n 何種類のものを * @param r いくつ並べるか * @param lim 1種類のものを選べる上限 * @return ModInt */ ModInt multiChoose(int n, int r, int lim) { ModInt ret = 0; for (int i = 0; i <= n; i++) { if (i * (lim + 1) > r) break; ret += ((i & 1) ? mod - 1 : 1) * combination(n, i) * multiChoose(n, r - i * (lim + 1)); } return ret; } } // namespace factorial /* #endregion */ /* #endregion */ /*</body>*/ #endif int N; LL A[212]; LL B[212]; int AI[212]; int BI[212]; LL latte[1123]; int malta = 0; // 積分 // 定数部は0 vector<ModInt> up(vector<ModInt> v) { for (int i : range(v.size())) { v[i] = v[i] / (i + 1); } reverse(ALL(v)); v.push_back(ModInt(0)); reverse(ALL(v)); return v; } // 多項式にxを代入 ModInt assign(vector<ModInt> v, ModInt x) { v = up(v); ModInt xx = 1; ModInt ret = 0; for (auto& it : v) { ret += it * xx; xx *= x; } return ret; } vector<ModInt> ad(vector<ModInt> x, vector<ModInt> y) { if (x.size() < y.size()) swap(x, y); for (int i : range(y.size())) { x[i] += y[i]; } return x; } ostream& operator<<(ostream& os, vector<ModInt> a) { os << "{"; for (auto& it : a) { os << *it << ","; } os << "}"; return os; } int main() { /* write here */ cin >> N; for (int i : range(N)) { cin >> A[i] >> B[i]; latte[malta++] = A[i]; latte[malta++] = B[i]; } sort(latte, latte + malta); malta = unique(latte, latte + malta) - latte; for (int i : range(N)) { AI[i] = lower_bound(latte, latte + malta, A[i]) - latte; BI[i] = lower_bound(latte, latte + malta, B[i]) - latte; } vector<vector<ModInt>> dp(malta - 1); { const int bg = AI[0]; const int ed = BI[0]; ModInt p = ModInt(1) / (B[0] - A[0]); for (int i : range(malta - 1)) { if (bg <= i && i + 1 <= ed) { dp[i] = {p}; } else { dp[i] = {ModInt(0)}; } } } // for (int j : range(malta - 1)) { // cerr << j << " " << dp[j] << endl; //} for (int i : range(1, N)) { ModInt p = ModInt(1) / (B[i] - A[i]); const int bg = AI[i]; const int ed = BI[i]; vector<vector<ModInt>> nxt(malta - 1); // 増える if (i % 2 == 1) { ModInt C = 0; for (int j : range(malta - 1)) { // cerr << i << " " << j << " " << *C << endl; if (bg <= j && j + 1 <= ed) { nxt[j] = up(dp[j]); nxt[j][0] -= assign(dp[j], ModInt(latte[j])); nxt[j][0] += C; for (auto& it : nxt[j]) it *= p; } else { nxt[j] = {ModInt(0)}; } C += assign(dp[j], ModInt(latte[j + 1])) - assign(dp[j], ModInt(latte[j])); } } // 減る else { ModInt C = 0; for (int j : !range(malta - 1)) { if (bg <= j && j + 1 <= ed) { nxt[j] = up(dp[j]); for (auto& it : nxt[j]) it = -it; nxt[j][0] += assign(dp[j], ModInt(latte[j + 1])); nxt[j][0] += C; for (auto& it : nxt[j]) it *= p; } else { nxt[j] = {ModInt(0)}; } C += assign(dp[j], ModInt(latte[j + 1])) - assign(dp[j], ModInt(latte[j])); } } swap(dp, nxt); // for (int j : range(malta - 1)) { // cerr << j << " " << dp[j] << endl; //} } ModInt ret = 0; for (int i : range(malta - 1)) { ret = ret + assign(dp[i], ModInt(latte[i + 1])) - assign(dp[i], ModInt(latte[i])); } cout << *ret << endl; return 0; }