QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#483606 | #4385. Random | chlyqwq# | AC ✓ | 16ms | 3632kb | C++23 | 14.2kb | 2024-07-18 20:18:58 | 2024-07-18 20:18:59 |
Judging History
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