QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#483606#4385. Randomchlyqwq#AC ✓16ms3632kbC++2314.2kb2024-07-18 20:18:582024-07-18 20:18:59

Judging History

你现在查看的是最新测评结果

  • [2024-07-18 20:18:59]
  • 评测
  • 测评结果:AC
  • 用时:16ms
  • 内存:3632kb
  • [2024-07-18 20:18:58]
  • 提交

answer

// K.cpp
// it is all my guess
// accepted plzzz!
// author : georgeyucjr
#include <bits/stdc++.h>

using ll = long long;
using ull = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using arr3 = std ::array<int, 3>;
using arr4 = std ::array<int, 4>;
using pii = std ::pair<int, int>;

#define ALL(vc) std ::begin(vc), std ::end(vc)
#define rep(i, f, t, ...) for (std ::decay<decltype(f + t)>::type i = f, _END_##i = t, ##__VA_ARGS__; i <= _END_##i; ++i)
#define per(i, f, t, ...) for (std ::decay<decltype(f + t)>::type i = f, _END_##i = t, ##__VA_ARGS__; i >= _END_##i; --i)
#define eb emplace_back
#define pb push_back
#define mkp make_pair
#define FILEIO(filename) freopen(filename ".in", "r", stdin), freopen(filename ".out", "w", stdout)
template <class T, class U> inline T ceil(T &&x, U &&y) { return (x > 0 ? (x + y - 1) / y : x / y); }
template <class T, class U> inline T floor(T &&x, U &&y) { return (x > 0 ? x / y : (x - y + 1) / y); }
template <class T, class U> inline T divmod(T &&x, U &&y) { auto &&q = floor(x, y); return mkp(q, x - q * y); }
template <class T> constexpr static T inf = std ::numeric_limits<T>::max() >> 1;
template <class T> inline int SZ(T &&x) { return x.size(); }
template <typename T> inline T Abs(const T &x) { return x < 0 ? -x : x; }
template <typename T> inline T sqr(const T &x) { return x * x; }
template <typename T> inline T Max(const T &x) { return x; }
template <typename T> inline T Min(const T &x) { return x; }
template <typename T, typename U, typename... Args> inline T Max(const T &x, const U &y, const Args &...args) { return x < y ? Max(y, args...) : Max(x, args...); }
template <typename T, typename U, typename... Args> inline T Min(const T &x, const U &y, const Args &...args) { return x < y ? Min(x, args...) : Min(y, args...); }
template <typename T, typename... Args> inline void chkmax(T &d, const Args &...x) { d = Max(d, x...); }
template <typename T, typename... Args> inline void chkmin(T &d, const Args &...x) { d = Min(d, x...); }

using namespace std;

#ifdef georgeyucjr
#include <georgeyucjr/debug.h>
#else
#define dbg(...) 36
#endif

namespace easy_IO {
inline void read(char &c) { c = getchar(); }
inline void read(string &str, bool is_move = false) { if (is_move) str += ' '; char c = getchar(); while (c != ' ' && c != '\n') str += c, c = getchar(); }
template <typename T> inline void read(T &x, bool is_unsigned = false) { x = 0; char ch = getchar(); if (is_unsigned) { while (ch < '0' || ch > '9') ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar ( ); } else { T _read_flag = (T)(1); while (ch < '0' || ch > '9') _read_flag = ch == '-' ? -1 : 1, ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar ( ); x *= _read_flag; } return void(); }
template <typename T> inline void read(vector<T> &v) { for (T &i : v) read(v); }
template <typename T, typename... Args> inline void read(T &x, Args&... args) { read(x), read(args...); }
template <typename T, typename U> inline void read(pair<T, U> &p) { read(p.first, p.second); }
template <typename T, typename U, typename V> inline void read(tuple<T, U, V> &t) { read(get<0>(t), get<1>(t), get<2>(t)); }
inline void write ( char c ) { putchar ( c ); }
inline void write ( string s ) { for (char c : s) putchar ( c ); }
template <typename T> inline void write(T x, bool is_unsigned = false) { if (!is_unsigned) if (x < 0) x = -x, putchar ('-'); if (x > 9) write(x / 10); putchar (x % 10 ^ '0'); }
template <typename T> inline void writeln(T x) { write (x), putchar('\n'); }
template <typename T> inline void writespc(T x) { write (x), putchar(' '); }
template <typename T, typename ... Args> inline void write(T x, Args ... args) { write(x), write(args...); }
template <typename T, typename ... Args> inline void writeln(T x, Args ... args) { write(x), putchar(' '), write(args...), putchar('\n'); }
template <typename T, typename ... Args> inline void writespc(T x, Args ... args) { write(x), putchar(' '), write(args...), putchar(' '); }
} // namespace easy_IO
using namespace easy_IO;

# ifndef GY_MMint
  # define GY_MMint

  namespace georgeyucjr
  {
    namespace internal
    {
      template <typename T>
      struct mkdbwd
      {
      };
      template <>
      struct mkdbwd<std ::uint8_t>
      {
        using type = std ::uint16_t;
      };
      template <>
      struct mkdbwd<std ::uint16_t>
      {
        using type = std ::uint32_t;
      };
      template <>
      struct mkdbwd<std ::uint32_t>
      {
        using type = std ::uint64_t;
      };
      template <>
      struct mkdbwd<std ::uint64_t>
      {
        using type = unsigned __int128;
      };
      template <typename T>
      using mkdbwd_t = mkdbwd<T>::type;
      inline constexpr auto flr(auto &&x, auto &&y)
      {
        return x / y - (x % y && (x ^ y) < 0);
      }
      inline constexpr auto divmod(auto x, auto y)
      {
        auto &&q = flr(x, y);
        return std::make_pair(q, x - q * y);
      }
    } // namespace internal

    using namespace internal;
    template <typename T>
    struct MontgomeryReduction
    {
      using int_type = T;
      using int_double_t = mkdbwd_t<T>;
      inline constexpr static int bsw = std::numeric_limits<T>::digits;
      inline constexpr explicit MontgomeryReduction(T mod)
          : _mod(mod),
            _mod_neg_inv(inv_base(~(mod - 1))),
            mbs((int_double_t(1) << bsw) % mod),
            mbs2(int_double_t(mbs) * mbs % mod),
            mbs3(int_double_t(mbs2) * mbs % mod) {}
      inline constexpr T mod() const { return _mod; }
      inline constexpr T mbase() const { return mbs; }
      inline constexpr T mbase2() const { return mbs2; }
      inline constexpr T mbase3() const { return mbs3; }
      inline constexpr T reduce(int_double_t t) const
      {
        return (t + int_double_t(T(t) * _mod_neg_inv) * _mod) >> bsw;
      }
      inline constexpr T unsafemod(T x) const { return x >= _mod * 2 ? x - _mod * 2 : x; }
      inline constexpr T safemod(T x) const { return x >= _mod ? x - _mod : x; }
      inline constexpr static T inv_base(T x)
      {
        T y = 1;
        for (int i = 1; i < bsw; i <<= 1)
          y *= 2 - x * y;
        return y;
      }

    private:
      T _mod, _mod_neg_inv, mbs, mbs2, mbs3;
    };
    template <std::unsigned_integral T, typename S = std::make_signed_t<T>>
    inline constexpr std::tuple<S, S, T> clc(T x, T y)
    {
      bool t = x < y;
      if (t)
        swap(x, y);
      if (y == 0)
      {
        if (x == 0)
          return {};
        if (t)
          return {0, 1, x};
        return {1, 0, x};
      }
      S s0 = 1, s1 = 0, t0 = 0, t1 = 1;
      while (true)
      {
        auto [q, r] = divmod(x, y);
        if (r == 0)
        {
          if (t)
            return {t1, s1, y} ;
          return {s1, t1, y};
        }
        S s2 = s0 - S(q) * s1, t2 = t0 - S(q) * t1;
        x = y,
        y = r,
        s0 = s1,
        s1 = s2,
        t0 = t1,
        t1 = t2;
      }
    }
    template <std::unsigned_integral T>
    inline constexpr T modinv(T x, T m)
    {
      auto [s, t, g] = clc(x, m);
      assert(g == 1);
      return s < 0 ? T(s) + m : s;
    }
    template <typename T>
    inline constexpr T Qpow(T a, auto b)
    {
      T ans{1};
      for (; b; b >>= 1, a *= a)
        if (b & 1)
          ans *= a;
      return ans;
    }
    template <typename Context>
    struct MontgomeryModInt
    {
      using mint = MontgomeryModInt;
      using int_type = Context::int_type;
      using mr_type = Context::mr_type;
      using int_double_t = mr_type::int_double_t;
      inline constexpr MontgomeryModInt() = default;
      inline constexpr MontgomeryModInt(long long y)
      {
        using S = std::make_signed_t<int_type>;
        S v = y % S(mod());
        x = mr().reduce(mr().mbase2() * int_double_t(v < 0 ? v + mod() : v));
      }
      inline constexpr MontgomeryModInt(int y)
      {
        using S = std::make_signed_t<int_type>;
        S v = y % S(mod());
        x = mr().reduce(mr().mbase2() * int_double_t(v < 0 ? v + mod() : v));
      }
      inline constexpr MontgomeryModInt(unsigned int y)
      {
        x = mr().reduce(mr().mbase2() * int_double_t(y % mod()));
      }
      inline constexpr MontgomeryModInt(unsigned long long y)
      {
        x = mr().reduce(mr().mbase2() * int_double_t(y % mod()));
      }
      inline constexpr int_type val() const { return mr().safemod(mr().reduce(x)); }
      inline constexpr int_type residue() const { return mr().safemod(x); }
      inline constexpr static int_type mod() { return mr().mod(); }
      inline constexpr mint &operator++()
      {
        x = mr().unsafemod(x + mr().mbase());
        return *this;
      }
      inline constexpr mint operator++(int)
      {
        mint r = *this;
        ++*this;
        return r;
      }
      inline constexpr mint &operator+=(const mint &rhs)
      {
        x = mr().unsafemod(x + rhs.x);
        return *this;
      }
      inline constexpr mint &operator--()
      {
        x = mr().unsafemod(x + mod() - mr().mbase());
        return *this;
      }
      inline constexpr mint operator--(int)
      {
        mint r = *this;
        --*this;
        return r;
      }
      inline constexpr mint &operator-=(const mint &rhs)
      {
        x = mr().unsafemod(x + mod() * 2 - rhs.x);
        return *this;
      }
      inline constexpr mint &operator*=(const mint &rhs)
      {
        x = mr().reduce(int_double_t(x) * rhs.x);
        return *this;
      }
      inline constexpr mint inv() const
      {
        return from_raw(
            mr().reduce(int_double_t(mr().mbase3()) * modinv(x, mod())));
      }
      inline constexpr mint pow(auto n) const { return Qpow(*this, n); }
      inline constexpr mint &operator/=(const mint &rhs) { return *this *= rhs.inv(); }
      inline constexpr mint operator+() const { return *this; }
      inline constexpr mint operator-() const { return from_raw(!x ? 0 : mod() * 2 - x); }
      inline friend constexpr mint operator+(mint lhs, const mint &rhs)
      {
        return lhs += rhs;
      }
      inline friend constexpr mint operator-(mint lhs, const mint &rhs)
      {
        return lhs -= rhs;
      }
      inline friend constexpr mint operator*(mint lhs, const mint &rhs)
      {
        return lhs *= rhs;
      }
      inline friend constexpr mint operator/(mint lhs, const mint &rhs)
      {
        return lhs /= rhs;
      }
      inline friend constexpr bool operator==(const mint &lhs, const mint &rhs)
      {
        return mr().safemod(lhs.x) == mr().safemod(rhs.x);
      }
      inline friend constexpr auto operator<=> (const mint &lhs, const mint &rhs)
      {
        return mr().safemod(lhs.x) <=> mr().safemod(rhs.x);
      }
      inline constexpr static mint from_raw(int_type x)
      {
        mint r;
        r.x = x;
        return r;
      }
      inline constexpr int_type raw() const { return x; }
  #ifdef __GEORGEYUCJR_READ__
      inline void write(IO &io) const { io.write(val()); }
  #else
      inline friend std::ostream &operator<<(std::ostream &os, const mint &x)
      {
        return os << x.val();
      }
  #endif
      inline constexpr static const mr_type &mr()
      {
        return Context::montgomery_reduction();
      }

    private:
      int_type x{};
    };
    template <std::unsigned_integral T, T Mod>
      requires(Mod % 2 == 1 && Mod <= std::numeric_limits<T>::max() / 2)
    struct StaticMontgomeryReductionContext
    {
      using int_type = T;
      using mr_type = MontgomeryReduction<T>;
      constexpr static const mr_type &montgomery_reduction() { return _reduction; }

    private:
      constexpr static auto _reduction = mr_type(Mod);
    };
    template <std::unsigned_integral T>
    struct DynamicMontgomeryReductionContext
    {
      using int_type = T;
      using mr_type = MontgomeryReduction<T>;
      struct Guard
      {
        Guard(const Guard &) = delete;
        Guard(Guard &&) = delete;
        Guard &operator=(const Guard &) = delete;
        Guard &operator=(Guard &&) = delete;
        ~Guard() { _reduction_env.pop_back(); }

      private:
        friend DynamicMontgomeryReductionContext;
        Guard() = default;
      };
      [[nodiscard]] inline static Guard set_mod(T mod)
      {
        assert(mod % 2 == 1 && mod <= std::numeric_limits<T>::max() / 4);
        _reduction_env.emplace_back(mod);
        return {};
      }
      inline constexpr static const mr_type &montgomery_reduction()
      {
        return _reduction_env.back();
      }

    private:
      inline static std ::vector<mr_type> _reduction_env;
    };

    template <std ::uint32_t Mod>
    using static_modint = MontgomeryModInt<StaticMontgomeryReductionContext<std ::uint32_t, Mod>>;

    template <std ::uint64_t Mod>
    using static_modint_64 = MontgomeryModInt<StaticMontgomeryReductionContext<std ::uint64_t, Mod>>;

    using modint998244353 = static_modint<998244353>;

    using modint1000000007 = static_modint<1000000007>;

  #define dymanic_modint_IN(_Tp, Mod)                                      \
    using dymanic_modint_type = DynamicMontgomeryReductionContext<_Tp>; \
    auto _guard = dymanic_modint_type ::set_mod();                      \
    using mint = MontgomeryModInt<dymanic_modint_type>;

  #define dymanic_modint(_Tp, Mod)                                      \
    using dymanic_modint_type = georgeyucjr::DynamicMontgomeryReductionContext<_Tp>; \
    auto _guard = dymanic_modint_type ::set_mod(Mod);                      \
    using mint = georgeyucjr::MontgomeryModInt<dymanic_modint_type>;
  } // namespace georgeyucjr

# endif

using mint = georgeyucjr :: modint1000000007;
signed main() {
  // ios_base ::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int T;
	read(T);
	auto slv = [&]() {
		int n, m;
		read(n, m);
		writeln((mint(n - m) / mint(2)).val());
	};
	while(T--) {
		slv();
	}

#if defined(LOCAL) && !defined(CPH)
  std::cerr << "Spend Time : " << clock() * 1. / CLOCKS_PER_SEC * 1e3 << " ms \n";
#endif
  return 0;
}


詳細信息

Test #1:

score: 100
Accepted
time: 16ms
memory: 3632kb

input:

100000
42 30
6335 1161
19170 15725
11479 6401
26963 24465
5706 5322
23282 16828
9962 492
2996 2955
4828 609
32392 14605
3903 154
293 77
17422 1295
19719 177
5448 5383
14772 11539
1870 1213
25668 632
17036 9895
28704 23812
31323 30334
17674 4665
15142 7712
28254 6869
25548 2097
32663 95
20038 12860
8...

output:

6
2587
500001726
2539
1249
192
3227
4735
500000024
500002113
500008897
500001878
108
500008067
9771
500000036
500001620
500000332
12518
500003574
2446
500000498
500006508
3715
500010696
500011729
16284
3589
3853
500013379
500004644
10174
119
49
500007944
500001824
500004584
4510
500006963
500010426
...

result:

ok 100000 lines