QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#394757 | #7782. Ursa Minor | wsyear | TL | 1522ms | 151732kb | C++17 | 5.5kb | 2024-04-20 19:12:23 | 2024-04-20 19:12:23 |
Judging History
answer
// Author: Klay Thompson
// Problem: # 7782. Ursa Minor
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
template<class T>inline void chkmn(T &x, T y) { if (y < x) x = y; }
template<class T>inline void chkmx(T &x, T y) { if (y > x) x = y; }
using namespace std;
template <int P>
class mod_int {
using Z = mod_int;
private:
static int mo(int x) { return x < 0 ? x + P : x; }
public:
int x;
int val() const { return x; }
mod_int() : x(0) {}
template <class T>
mod_int(const T &x_) : x(x_ >= 0 && x_ < P ? static_cast<int>(x_) : mo(static_cast<int>(x_ % P))) {}
bool operator==(const Z &rhs) const { return x == rhs.x; }
bool operator!=(const Z &rhs) const { return x != rhs.x; }
Z operator-() const { return Z(x ? P - x : 0); }
Z pow(long long k) const {
Z res = 1, t = *this;
while (k) {
if (k & 1) res *= t;
if (k >>= 1) t *= t;
}
return res;
}
Z &operator++() {
x < P - 1 ? ++x : x = 0;
return *this;
}
Z &operator--() {
x ? --x : x = P - 1;
return *this;
}
Z operator++(int) {
Z ret = x;
x < P - 1 ? ++x : x = 0;
return ret;
}
Z operator--(int) {
Z ret = x;
x ? --x : x = P - 1;
return ret;
}
Z inv() const { return pow(P - 2); }
Z &operator+=(const Z &rhs) {
(x += rhs.x) >= P && (x -= P);
return *this;
}
Z &operator-=(const Z &rhs) {
(x -= rhs.x) < 0 && (x += P);
return *this;
}
Z &operator*=(const Z &rhs) {
x = 1ULL * x * rhs.x % P;
return *this;
}
Z &operator/=(const Z &rhs) { return *this *= rhs.inv(); }
#define setO(T, o) \
friend T operator o(const Z &lhs, const Z &rhs) {\
Z res = lhs; \
return res o## = rhs; \
}
setO(Z, +) setO(Z, -) setO(Z, *) setO(Z, /)
#undef setO
};
const int P = 1011451423;
using Z = mod_int<P>;
const int maxn = 200010;
const int maxm = 100;
const int B = 80;
const Z iv2 = Z(2).inv();
const Z iv6 = Z(6).inv();
int n, m, q, d[maxn], st[maxn][20];
ll a[maxn], pool[maxn * maxm], *used = pool;
struct fwt {
int n;
ll *t;
fwt() { }
fwt(int m) { n = m, t = used, used += m + 3; }
void upd(int x, ll v) {
while (x <= n) t[x] += v, x += x & (-x);
}
ll qry(int x) {
ll res = 0;
while (x) res += t[x], x -= x & (-x);
return res;
}
} t[maxm][maxm];
struct FWT {
Z t[maxn];
void upd(int x, Z v) {
x++;
while (x <= n) t[x] += v, x += x & (-x);
}
Z qry(int x) {
x++;
Z res = 0;
while (x) res += t[x], x -= x & (-x);
return res;
}
} t0, t1, t2;
Z sum(int n) {
return Z(n) * (n + 1) * iv2;
}
Z sum2(int n) {
return Z(n) * (n + 1) * (2 * n + 1) * iv6;
}
int que(int l, int r) {
int k = __lg(r - l + 1);
return gcd(st[l][k], st[r - (1 << k) + 1][k]);
}
int main() {
cin.tie(nullptr) -> ios::sync_with_stdio(false);
cin >> n >> m >> q;
rep (i, 0, n - 1) cin >> a[i];
rep (i, 1, m) cin >> st[i][0];
rep (j, 1, 19) rep (i, 1, m - (1 << j) + 1)
st[i][j] = gcd(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
rep (i, 1, B) rep (j, 0, i - 1) t[i][j] = fwt(n / i + 5);
rep (i, 0, n - 1) rep (j, 1, B) t[j][i % j].upd(i / j + 1, a[i]);
rep (i, 0, n - 1) t0.upd(i, Z(a[i])), t1.upd(i, Z(i) * a[i]), t2.upd(i, Z(i) * i * a[i]);
while (q--) {
string op;
cin >> op;
if (op == "U") {
int x;
cin >> x, x--;
rep (i, 1, B) t[i][x % i].upd(x / i + 1, -a[x]);
t0.upd(x, -Z(a[x])), t1.upd(x, -Z(x) * a[x]), t2.upd(x, -Z(x) * x * a[x]);
cin >> a[x];
rep (i, 1, B) t[i][x % i].upd(x / i + 1, a[x]);
t0.upd(x, Z(a[x])), t1.upd(x, Z(x) * a[x]), t2.upd(x, Z(x) * x * a[x]);
} else {
int l, r, S, T, ok = 1;
cin >> l >> r >> S >> T, l--, r--;
int g = gcd(r - l + 1, que(S, T));
ll lst = 0;
if (g <= B) {
ll lst = 0;
bool ok = 1;
rep (i, 0, g - 1) {
ll L = l + i, R = r - g + i + 1, rg = L % g;
ll sum = t[g][rg].qry(R / g + 1) - t[g][rg].qry(L / g);
if (i && sum != lst) { ok = 0; break; }
lst = sum;
}
cout << (ok ? "Yes" : "No") << '\n';
} else if (r - l + 1 <= 500) {
rep (i, 0, g - 1) {
ll sum = 0;
for (int j = l + i; j <= r; j += g) sum += a[j];
if (i) ok &= (sum == lst);
if (!ok) break;
lst = sum;
}
cout << (ok ? "Yes" : "No") << '\n';
} else {
Z ss0 = 0, ss1 = 0, ss2 = 0;
for (int pl = l, pr = l + g - 1; pr <= r; pl += g, pr += g) {
Z s0 = t0.qry(pr) - t0.qry(pl), s1 = t1.qry(pr) - t1.qry(pl), s2 = t2.qry(pr) - t2.qry(pl);
Z rs0 = s0, rs1 = s1 - s0 * pl, rs2 = s2 - rs1 * pl * 2 - s0 * pl * pl;
rs0 -= Z(a[pl]) * (g - 1), rs1 -= Z(a[pl]) * sum(g - 1), rs2 -= Z(a[pl]) * sum2(g - 1);
ss0 += rs0, ss1 += rs1, ss2 += rs2;
}
if ((ss0.val() || ss1.val() || ss2.val())) cout << "No\n";
else cout << "Yes\n";
}
}
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 11672kb
input:
6 4 5 1 1 4 5 1 4 3 3 2 4 Q 1 5 1 2 Q 2 5 3 4 U 5 2 Q 1 6 1 2 Q 2 5 3 4
output:
Yes No No Yes
result:
ok 4 tokens
Test #2:
score: 0
Accepted
time: 2ms
memory: 11320kb
input:
1 1 1 0 1 Q 1 1 1 1
output:
Yes
result:
ok "Yes"
Test #3:
score: 0
Accepted
time: 184ms
memory: 13560kb
input:
2000 2000 200000 1 1 2 0 0 2 0 2 0 0 0 0 0 2 2 1 2 0 0 2 2 2 1 0 1 2 1 2 0 0 1 1 1 2 0 0 2 2 2 2 0 2 0 0 2 1 2 0 0 1 2 2 1 0 2 0 0 0 1 2 2 1 2 2 0 0 1 1 1 0 0 2 0 0 1 1 0 2 2 2 1 0 0 1 0 1 2 2 2 1 1 2 2 1 2 1 0 2 2 3 1 3 2 3 1 0 1 2 0 1 1 1 0 2 2 3 2 0 3 2 3 3 1 2 3 1 2 0 1 0 3 1 0 0 2 0 1 2 1 3 2 2...
output:
Yes Yes No Yes Yes No No No Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes No Yes Yes No No No No No Yes No No No Yes Yes No Yes No Yes Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes No Yes Yes Yes No No Yes No Yes No No No Yes Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes No...
result:
ok 100554 tokens
Test #4:
score: 0
Accepted
time: 112ms
memory: 26320kb
input:
1 200000 200000 998244353 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes ...
result:
ok 100240 tokens
Test #5:
score: 0
Accepted
time: 106ms
memory: 21376kb
input:
6 131072 200000 0 0 0 0 1000000000 1000000000 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 ...
output:
Yes Yes Yes No No No Yes No No No No No Yes Yes No Yes No Yes Yes Yes No No No No No No No Yes No No No Yes Yes Yes Yes Yes Yes Yes Yes No No No No Yes Yes No No No No No No No No No No No No No No No No No No No Yes No No No No No No No No No No No No No No No Yes No No No No No No Yes Yes No Yes N...
result:
ok 100021 tokens
Test #6:
score: 0
Accepted
time: 1204ms
memory: 151236kb
input:
200000 200000 200000 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877...
output:
No No No No No No No No No No No No No No Yes No No No Yes No No No No No No No No No No No No No No Yes No No No No No Yes Yes Yes No No No No No No No No Yes No No No No No No No No No Yes No No No No No No No No No No No No No No No No No No No No No No No Yes No Yes Yes No No No No No No No No N...
result:
ok 187340 tokens
Test #7:
score: 0
Accepted
time: 1462ms
memory: 151732kb
input:
200000 200000 200000 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531...
output:
Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes ...
result:
ok 199985 tokens
Test #8:
score: 0
Accepted
time: 1503ms
memory: 150864kb
input:
200000 200000 200000 793134805 922104801 158394038 993313213 77527653 992889267 148461787 499165677 132176015 189185554 783374975 332147281 923925325 371040161 393285793 437388761 138662855 212488140 265392646 498903298 578518594 550390771 960084339 408548934 56106823 814997309 456913457 300689692 1...
output:
No No No No No No No No No No No No Yes No No No No No No No No No No No No No No No No No No No No No No No No No No No Yes No No No No No No No Yes No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No Yes No...
result:
ok 200000 tokens
Test #9:
score: 0
Accepted
time: 1522ms
memory: 150968kb
input:
200000 200000 200000 451942037 451942036 451942035 451942037 451942036 451942035 451942037 451942036 451942035 451942037 451942036 451942035 451942037 451942036 451942035 451942037 451942036 451942035 451942037 451942036 451942035 451942037 451942036 451942035 451942037 451942036 451942035 451942037...
output:
No No No No Yes No Yes No No No No Yes No No No Yes No Yes No No No No No No No No No No No No No No Yes No No No No No No No Yes No No Yes No Yes No Yes No Yes No No No No Yes No No Yes No No No No No No No No Yes No Yes No No No No Yes No Yes No No Yes No Yes No No No Yes No No No No No No No No N...
result:
ok 199977 tokens
Test #10:
score: 0
Accepted
time: 1195ms
memory: 151160kb
input:
200000 200000 200000 606894463 710609424 913364361 30426550 801940265 516097169 349718376 606894463 710609424 913364361 30426550 801940265 516097169 349718376 606894463 710609424 913364361 30426550 801940265 516097169 349718376 606894463 710609424 913364361 30426550 801940265 516097169 349718376 606...
output:
No No No Yes No No No No No No No No No No No No Yes No No Yes No No No No No No No No No No Yes No No No No Yes No No No No No No No No Yes No No No No No No No No No No No No Yes No No No Yes No No No No No No No Yes No No No No No No No No No Yes No No No No No No No No No Yes No No No No No No N...
result:
ok 100329 tokens
Test #11:
score: -100
Time Limit Exceeded
input:
200000 199999 200000 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886...
output:
Yes No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No...