結果
問題 |
No.1201 お菓子配り-4
|
ユーザー |
|
提出日時 | 2025-07-24 14:27:06 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3,045 ms / 4,000 ms |
コード長 | 7,643 bytes |
コンパイル時間 | 3,183 ms |
コンパイル使用メモリ | 281,484 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-07-24 14:27:28 |
合計ジャッジ時間 | 21,541 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 36 |
ソースコード
#include <bits/stdc++.h> using namespace std; template <class F> class y_combinator { F f; public: y_combinator(F&& f) : f(std::forward<F>(f)) {} template <class... Args> auto operator()(Args&&... args) const { return f(*this, std::forward<Args>(args)...); } }; using ll = long long; using ld = long double; template <class T, class U = std::less<T>> using prique = std::priority_queue<T, std::vector<T>, U>; template <class T> T floor(T a, T b) noexcept { return a / b - (a % b && (a ^ b) < 0); } template <class T> T ceil(T a, T b) noexcept { return floor(a + b - 1, b); } template <class T> bool chmin(T& x, const T& y) noexcept { return (x > y ? x = y, true : false); } template <class T> bool chmax(T& x, const T& y) noexcept { return (x < y ? x = y, true : false); } #define overload4(a, b, c, d, e, ...) e #define rep1(a) for (long long _i = 0; _i < (a); _i++) #define rep2(i, a) for (long long i = 0; i < (a); i++) #define rep3(i, a, b) for (long long i = (a); i < (b); i++) #define rep4(i, a, b, c) for (long long i = (a); i < (b); i += (c)) #define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__) #define rrep(i, a, b, c) for (long long i = (a); i > (b); i += (c)) #define all(x) std::begin(x), std::end(x) #define rall(x) std::rbegin(x), std::rend(x) #define pb push_back #ifndef LOCAL #define debug(...) #endif #include <atcoder/math> namespace internal { constexpr long long safe_mod(long long x, long long m) { x %= m; if (x < 0) x += m; return x; } constexpr long long pow_mod_constexpr(long long x, long long n, int m_) { if (m_ == 1) return 0; unsigned int m = static_cast<unsigned int>(m_); unsigned long long r = 1, y = safe_mod(x, m); while (n) { if (n & 1) { r = (r * y) % m; } y = (y * y) % m; n >>= 1; } return r; } constexpr bool is_prime_constexpr(int n) { if (n <= 1) return false; if (n == 2 || n == 7 || n == 61) return true; if (n % 2 == 0) return false; long long t = n - 1; while (t % 2 == 0) t /= 2; constexpr long long base[3] = {2, 7, 61}; for (long long a : base) { long long d = t; long long v = pow_mod_constexpr(a, t, n); if (v == 1) continue; while (d != n - 1 && v != n - 1) { v = v * v % n; d <<= 1; } if (v != n - 1) return false; } return true; } template <int n> constexpr bool is_prime = is_prime_constexpr(n); constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) { a = safe_mod(a, b); if (a == 0) return {b, 0}; long long s = b, t = a; long long m0 = 0, m1 = 1; while (t) { long long u = s / t; s -= t * u; m0 -= m1 * u; auto tmp = s; s = t; t = tmp; tmp = m0; m0 = m1; m1 = tmp; } if (m0 < 0) m0 += b / s; return {s, m0}; } constexpr long long inv_mod(long long x, long long m) { assert(1 <= m); auto z = inv_gcd(x, m); assert(z.first == 1); return z.second; } constexpr int primitive_root_constexpr(int m) { if (m == 2) return 1; if (m == 167772161) return 3; if (m == 469762049) return 3; if (m == 754974721) return 11; if (m == 998244353) return 3; int divs[20] = {}; divs[0] = 2; int cnt = 1; int x = (m - 1) / 2; while (x % 2 == 0) x /= 2; for (int i = 3; i <= x / i; i += 2) { if (x % i == 0) { divs[cnt++] = i; while (x % i == 0) x /= i; } } if (x > 1) divs[cnt++] = x; for (int g = 2;; g++) { bool ok = true; for (int i = 0; i < cnt; i++) { if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) { ok = false; break; } } if (ok) return g; } } template <int m> constexpr int primitive_root = primitive_root_constexpr(m); unsigned long long floor_sum_unsigned(unsigned long long n, unsigned long long m, unsigned long long a, unsigned long long b) { unsigned long long ans = 0; while (true) { if (a >= m) { ans += n * (n - 1) / 2 * (a / m); a %= m; } if (b >= m) { ans += n * (b / m); b %= m; } unsigned long long y_max = a * n + b; if (y_max < m) break; n = (unsigned long long)(y_max / m); b = (unsigned long long)(y_max % m); std::swap(m, a); } return ans; } } // namespace internal template <unsigned m> class StaticModint { unsigned value; using mint = StaticModint; static constexpr bool is_prime = internal::is_prime<m>; static constexpr unsigned umod() { return m; } public: static constexpr unsigned mod() { return m; } static mint raw(int v) { mint x; x.value = v; return x; } StaticModint() : value(0) {} template <class T, std::enable_if_t<std::is_integral_v<T>, int> = false> StaticModint(T v) { value = static_cast<unsigned>(internal::safe_mod(v, m)); } int val() const { return value; } mint& operator++() { value = (value + 1 == umod() ? 0 : value + 1); return *this; } mint& operator--() { value = (value == 0 ? umod() - 1 : value - 1); return *this; } mint operator++(int) { mint res = *this; ++*this; return res; } mint operator--(int) { mint res = *this; --*this; return res; } mint& operator+=(const mint& rhs) { value += rhs.value; if (value >= umod()) value -= umod(); return *this; } mint& operator-=(const mint& rhs) { if (value < rhs.value) value += umod(); value -= rhs.value; return *this; } mint& operator*=(const mint& rhs) { unsigned long long z = value; z *= rhs.value; value = static_cast<unsigned>(z % umod()); return *this; } mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); } mint operator+() const { return *this; } mint operator-() const { return mint() - *this; } mint pow(long long n) const { assert(0 <= n); mint x = *this, r = 1; for (; n; n >>= 1, x *= x) if (n & 1) r *= x; return r; } mint inv() const { return (is_prime ? pow(m - 2) : internal::inv_mod(value, m)); } friend mint operator+(const mint& lhs, const mint& rhs) { return mint(lhs) += rhs; } friend mint operator-(const mint& lhs, const mint& rhs) { return mint(lhs) -= rhs; } friend mint operator*(const mint& lhs, const mint& rhs) { return mint(lhs) *= rhs; } friend mint operator/(const mint& lhs, const mint& rhs) { return mint(lhs) /= rhs; } friend bool operator==(const mint& lhs, const mint& rhs) { return lhs.value == rhs.value; } friend bool operator!=(const mint& lhs, const mint& rhs) { return lhs.value != rhs.value; } template <class Pr> void print(Pr& p) const { p << value; } template <class Sc> void scan(Sc& s) { s >> value; } }; using modint998 = StaticModint<998244353>; using modint107 = StaticModint<1000000007>; using mint = modint107; int main() { int N, M; cin >> N >> M; vector<int> A(N), B(M); rep(i, N) cin >> A[i]; rep(i, M) cin >> B[i]; mint ans = 0; rep(i, N) rep(j, M) { mint t = atcoder::floor_sum(B[j], B[j], A[i], A[i]); ans += t * 2; } cout << ans.val() << "\n"; }