結果
| 問題 |
No.1201 お菓子配り-4
|
| コンテスト | |
| ユーザー |
 SHIJOU
|
| 提出日時 | 2020-09-22 20:43:34 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,115 bytes |
| コンパイル時間 | 1,813 ms |
| コンパイル使用メモリ | 195,764 KB |
| 最終ジャッジ日時 | 2025-01-14 19:37:37 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 35 TLE * 1 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:213:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
213 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
main.cpp:214:24: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
214 | rep(i, n) scanf("%d", a+i);
| ~~~~~^~~~~~~~~~~
main.cpp:215:24: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
215 | rep(i, m) scanf("%d", b+i);
| ~~~~~^~~~~~~~~~~
ソースコード
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQG = priority_queue<T, vector<T>, greater<T> >;
const int INF = 0xccccccc;
const ll LINF = 0xcccccccccccccccLL;
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);}
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);}
template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second;}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << p.first << ' ' << p.second;}
struct barrett {
unsigned int _m;
uint64_t im;
barrett(unsigned int m):_m(m), im(uint64_t(-1)/m + 1) {}
unsigned int umod() const {return _m;}
unsigned int mul(unsigned int a, unsigned int b) const {
uint64_t z = a;
z *= b;
uint64_t x = uint64_t(((unsigned __int128)(z)*im) >> 64);
unsigned int v = (unsigned int)(z-x*_m);
if(_m <= v) v += _m;
return v;
}
};
constexpr int64_t safe_mod(int64_t x, int64_t m) {
x %= m;
if(x < 0) x += m;
return x;
}
constexpr pair<int64_t, int64_t> inv_gcd(int64_t a, int64_t b) {
a = safe_mod(a, b);
if(a == 0) return {b, 0};
int64_t s = b, t = a;
int64_t m0 = 0, m1 = 1;
while(t) {
int64_t u = s/t;
s -= t*u;
m0 -= m1*u;
int64_t tmp = s;
s = t;
t = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
if(m0 < 0) m0 += b/s;
return {s, m0};
}
int64_t pow_mod(int64_t x, int64_t n, int m) {
if(m == 1) return 0;
barrett bt((unsigned int)(m));
unsigned int r = 1, y = (unsigned int)(safe_mod(x, m));
while(n) {
if(n&1) r = bt.mul(r, y);
y = bt.mul(y, y);
n >>= 1;
}
return r;
}
int64_t inv_mod(int64_t x, int64_t m) {
pair<int64_t, int64_t> z = inv_gcd(x, m);
assert(z.first == 1);
return z.second;
}
//(y, z) answer mod z = y, 無理な時は(-1, -1)
pair<int64_t, int64_t> crt(const vector<int64_t> &r, const vector<int64_t> &m) {
int n = int(r.size());
int64_t r0 = 0, m0 = 1;
for(int i = 0; i < n; i++) {
assert(1 <= m[i]);
int64_t r1 = safe_mod(r[i], m[i]), m1 = m[i];
if(m0 < m1) {
swap(r0, r1);
swap(m0, m1);
}
if(m0 % m1 == 0) {
if(r0 % m1 != r1) return {-1, -1};
continue;
}
int64_t g, im;
tie(g, im) = inv_gcd(m0, m1);
int64_t u1 = (m1/g);
if((r1-r0)%g) return {-1, -1};
int64_t x = (r1-r0)/g%u1 * im % u1;
r0 += x*m0;
m0 *= u1;
if(r0 < 0) r0 += m0;
}
return {r0, m0};
}
//[0, n) (a*i+b)/m
int64_t floor_sum(int64_t n, int64_t m, int64_t a, int64_t b) {
int64_t ans = 0;
if(a >= m) {
ans += ((n-1)*n>>1)*(a/m);
a %= m;
}
if(b >= m) {
ans += n*(b/m);
b %= m;
}
int64_t y_max = (a*n+b)/m, x_max = y_max*m-b;
if(y_max == 0) return ans;
ans += (n - (x_max+a-1)/a) * y_max;
ans += floor_sum(y_max, a, m, (a - x_max%a)%a);
return ans;
}
const unsigned int mod = 1000000007;
//const unsigned int mod = 998244353;
struct mint {
unsigned int x;
mint():x(0) {}
mint(int64_t x_) {
int64_t v = int64_t(x_ % mod);
if(v < 0) v += mod;
x = (unsigned int)v;
}
static mint row(int v) {
mint v_;
v_.x = v;
return v_;
}
mint operator-() const { return mint(-x);}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
uint64_t z = x;
z *= a.x;
x = (unsigned int)(z % mod);
return *this;
}
mint operator+(const mint a) const { return mint(*this) += a;}
mint operator-(const mint a) const { return mint(*this) -= a;}
mint operator*(const mint a) const { return mint(*this) *= a;}
friend bool operator==(const mint &a, const mint &b) {return a.x == b.x;}
friend bool operator!=(const mint &a, const mint &b) {return a.x != b.x;}
mint &operator++() {
x++;
if(x == mod) x = 0;
return *this;
}
mint &operator--() {
if(x == 0) x = mod;
x--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint pow(int64_t t) const {
mint x_ = *this, r = 1;
while(t) {
if(t&1) r *= x_;
x_ *= x_;
t >>= 1;
}
return r;
}
//for prime mod
mint inv() const { return pow(mod-2);}
mint& operator/=(const mint a) { return *this *= a.inv();}
mint operator/(const mint a) {return mint(*this) /= a;}
};
istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
#define N 2010
//head
int n, m;
int a[N], b[N];
mint ans;
int main() {
scanf("%d%d", &n, &m);
rep(i, n) scanf("%d", a+i);
rep(i, m) scanf("%d", b+i);
rep(i, n) rep(j, m) {
ans += floor_sum(b[j]+1, b[j], a[i], 0)<<1;
}
cout << ans << endl;
}