| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 893749 | Alcabel | 송금 (JOI19_remittance) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
const long long mod = 1e9 + 7;
#else
const long long mod = 2000000000000021ll;
#endif
#ifdef LOCAL
typedef long long __int128_t;
#endif
struct Modint {
long long x;
Modint() {
x = 0ll;
}
Modint(long long _x) {
while (_x >= mod) {
_x -= mod;
}
while (_x < 0) {
_x += mod;
}
x = _x;
}
Modint(__int128_t _x) {
if (_x >= mod || _x <= -mod) {
_x %= mod;
}
if (_x < 0) {
_x += mod;
}
x = _x;
}
Modint operator+(const Modint& other) const {
return Modint(x + other.x);
}
Modint operator-(const Modint& other) const {
return Modint(x - other.x);
}
Modint operator*(const Modint& other) const {
return Modint((__int128_t)x * other.x);
}
void operator+=(const Modint& other) {
*this = *this + other;
}
void operator-=(const Modint& other) {
*this = *this - other;
}
void operator*=(const Modint& other) {
*this = *this * other;
}
Modint operator^(long long k) const {
Modint tmp = x, res = 1ll;
while (k > 0) {
// cerr << k << '\n';
if (k & 1ll) {
res *= tmp;
}
tmp *= tmp;
k >>= 1;
}
return res;
}
~Modint() {}
};
void solve() {
int n;
cin >> n;
vector<int> a(n), b(n);
for (int i = 0; i < n; ++i) {
cin >> a[i] >> b[i];
}
Modint denom = 1ll;
for (int i = 0; i < n; ++i) {
denom = denom + denom;
}
// cerr << denom.x << '\n';
denom = (denom - 1ll) ^ (mod - 2);
// cerr << (denom * ((1ll << n) - 1)).x << '\n';
vector<Modint> two(n + 1);
two[0] = 1;
for (int i = 1; i <= n; ++i) {
two[i] = two[i - 1] + two[i - 1];
}
vector<Modint> pref(n + 1), suf(n + 1);
pref[0] = 0, suf[0] = 0;
for (int i = 1; i <= n; ++i) {
pref[i] = pref[i - 1] + pref[i - 1] + (long long)(b[i - 1] - a[i - 1]);
}
for (int i = n - 1; i >= 0; --i) {
suf[i] = suf[i + 1] + two[n - 1 - i] * (long long)(b[i] - a[i]);
}
vector<long long> x(n);
for (int i = 0; i < n; ++i) {
Modint xmod = pref[i + 1] + suf[i + 1] * two[i + 1];
/*for (int j = i; j >= 0; --j) {
xmod = xmod + xmod + (long long)(b[j] - a[j]);
}
for (int j = n - 1; j > i; --j) {
xmod = xmod + xmod + (long long)(b[j] - a[j]);
}*/
xmod = (Modint(0ll) - xmod) * denom;
if (xmod.x > mod / 2) {
cout << "No\n";
return;
}
x[i] = xmod.x;
}
for (int i = 0, prv = n - 1; i < n; ++i, ++prv) {
if (prv == n) { prv = 0; }
if (x[prv] - 2 * x[i] != b[i] - a[i]) {
cout << "No\n";
return;
}
}
bool change = true;
while (change) {
change = false;
for (int i = 0; i < n; ++i) {
if (x[i] > 0 && a[i] >= 2) {
change = true;
long long trans = min(x[i], a[i] * 1ll / 2);
x[i] -= trans;
a[i] -= 2 * trans;
int nxt = i + 1;
if (nxt == n) {
nxt = 0;
}
a[nxt] += trans;
}
}
}
for (int i = 0; i < n; ++i) {
if (x[i] != 0) {
cout << "No\n";
return;
}
}
cout << "Yes\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int T = 1;
cin >> T;
while (T--) {
solve();
cerr << "-----------\n";
cout << "-----------\n";
}
#else
int T = 1;
// cin >> T;
while (T--) {
solve();
}
#endif
return 0;
}
/*
2000000000000021
2000000000000077
2000000000000081
*/