QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#260380 | #7839. 虹 | hos_lyric# | 10 | 29ms | 3992kb | C++14 | 10.6kb | 2023-11-22 06:21:07 | 2024-07-04 03:08:12 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
////////////////////////////////////////////////////////////////////////////////
template <unsigned M_> struct ModInt {
static constexpr unsigned M = M_;
unsigned x;
constexpr ModInt() : x(0U) {}
constexpr ModInt(unsigned x_) : x(x_ % M) {}
constexpr ModInt(unsigned long long x_) : x(x_ % M) {}
constexpr ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
constexpr ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
ModInt &operator*=(const ModInt &a) { x = (static_cast<unsigned long long>(x) * a.x) % M; return *this; }
ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
ModInt pow(long long e) const {
if (e < 0) return inv().pow(-e);
ModInt a = *this, b = 1U; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
}
ModInt inv() const {
unsigned a = M, b = x; int y = 0, z = 1;
for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; }
assert(a == 1U); return ModInt(y);
}
ModInt operator+() const { return *this; }
ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0U; return a; }
ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
explicit operator bool() const { return x; }
bool operator==(const ModInt &a) const { return (x == a.x); }
bool operator!=(const ModInt &a) const { return (x != a.x); }
friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
};
////////////////////////////////////////////////////////////////////////////////
constexpr unsigned MO = 20242024;
using Mint = ModInt<MO>;
struct Hld {
int n, rt;
// needs to be tree
// vertex lists
// modified in build(rt) (parent removed, heavy child first)
vector<vector<int>> graph;
vector<int> sz, par, dep;
int zeit;
vector<int> dis, fin, sid;
// head vertex (minimum depth) in heavy path
vector<int> head;
Hld() : n(0), rt(-1), zeit(0) {}
explicit Hld(int n_) : n(n_), rt(-1), graph(n), zeit(0) {}
void ae(int u, int v) {
assert(0 <= u); assert(u < n);
assert(0 <= v); assert(v < n);
graph[u].push_back(v);
graph[v].push_back(u);
}
void dfsSz(int u) {
sz[u] = 1;
for (const int v : graph[u]) {
auto it = std::find(graph[v].begin(), graph[v].end(), u);
if (it != graph[v].end()) graph[v].erase(it);
par[v] = u;
dep[v] = dep[u] + 1;
dfsSz(v);
sz[u] += sz[v];
}
}
void dfsHld(int u) {
dis[u] = zeit++;
const int deg = graph[u].size();
if (deg > 0) {
int vm = graph[u][0];
int jm = 0;
for (int j = 1; j < deg; ++j) {
const int v = graph[u][j];
if (sz[vm] < sz[v]) {
vm = v;
jm = j;
}
}
swap(graph[u][0], graph[u][jm]);
head[vm] = head[u];
dfsHld(vm);
for (int j = 1; j < deg; ++j) {
const int v = graph[u][j];
head[v] = v;
dfsHld(v);
}
}
fin[u] = zeit;
}
void build(int rt_) {
assert(0 <= rt_); assert(rt_ < n);
rt = rt_;
sz.assign(n, 0);
par.assign(n, -1);
dep.assign(n, -1);
dep[rt] = 0;
dfsSz(rt);
zeit = 0;
dis.assign(n, -1);
fin.assign(n, -1);
head.assign(n, -1);
head[rt] = rt;
dfsHld(rt);
assert(zeit == n);
sid.assign(n, -1);
for (int u = 0; u < n; ++u) sid[dis[u]] = u;
}
friend ostream &operator<<(ostream &os, const Hld &hld) {
const int maxDep = *max_element(hld.dep.begin(), hld.dep.end());
vector<string> ss(2 * maxDep + 1);
int pos = 0, maxPos = 0;
for (int j = 0; j < hld.n; ++j) {
const int u = hld.sid[j];
const int d = hld.dep[u];
if (hld.head[u] == u) {
if (j != 0) {
pos = maxPos + 1;
ss[2 * d - 1].resize(pos, '-');
ss[2 * d - 1] += '+';
}
} else {
ss[2 * d - 1].resize(pos, ' ');
ss[2 * d - 1] += '|';
}
ss[2 * d].resize(pos, ' ');
ss[2 * d] += std::to_string(u);
if (maxPos < static_cast<int>(ss[2 * d].size())) {
maxPos = ss[2 * d].size();
}
}
for (int d = 0; d <= 2 * maxDep; ++d) os << ss[d] << '\n';
return os;
}
bool contains(int u, int v) const {
return (dis[u] <= dis[v] && dis[v] < fin[u]);
}
int lca(int u, int v) const {
assert(0 <= u); assert(u < n);
assert(0 <= v); assert(v < n);
for (; head[u] != head[v]; ) (dis[u] > dis[v]) ? (u = par[head[u]]) : (v = par[head[v]]);
return (dis[u] > dis[v]) ? v : u;
}
int jumpUp(int u, int d) const {
assert(0 <= u); assert(u < n);
assert(d >= 0);
if (dep[u] < d) return -1;
const int tar = dep[u] - d;
for (u = head[u]; ; u = head[par[u]]) {
if (dep[u] <= tar) return sid[dis[u] + (tar - dep[u])];
}
}
int jump(int u, int v, int d) const {
assert(0 <= u); assert(u < n);
assert(0 <= v); assert(v < n);
assert(d >= 0);
const int l = lca(u, v);
const int du = dep[u] - dep[l], dv = dep[v] - dep[l];
if (d <= du) {
return jumpUp(u, d);
} else if (d <= du + dv) {
return jumpUp(v, du + dv - d);
} else {
return -1;
}
}
// [u, v) or [u, v]
template <class F> void doPathUp(int u, int v, bool inclusive, F f) const {
assert(contains(v, u));
for (; head[u] != head[v]; u = par[head[u]]) f(dis[head[u]], dis[u] + 1);
if (inclusive) {
f(dis[v], dis[u] + 1);
} else {
if (v != u) f(dis[v] + 1, dis[u] + 1);
}
}
// not path order, include lca(u, v) or not
template <class F> void doPath(int u, int v, bool inclusive, F f) const {
const int l = lca(u, v);
doPathUp(u, l, false, f);
doPathUp(v, l, inclusive, f);
}
// (vs, ps): compressed tree
// vs: DFS order (sorted by dis)
// vs[ps[x]]: the parent of vs[x]
// ids[vs[x]] = x, not set for non-tree vertex
vector<int> ids;
pair<vector<int>, vector<int>> compress(vector<int> us) {
// O(n) first time
ids.resize(n, -1);
std::sort(us.begin(), us.end(), [&](int u, int v) -> bool {
return (dis[u] < dis[v]);
});
us.erase(std::unique(us.begin(), us.end()), us.end());
int usLen = us.size();
assert(usLen >= 1);
for (int x = 1; x < usLen; ++x) us.push_back(lca(us[x - 1], us[x]));
std::sort(us.begin(), us.end(), [&](int u, int v) -> bool {
return (dis[u] < dis[v]);
});
us.erase(std::unique(us.begin(), us.end()), us.end());
usLen = us.size();
for (int x = 0; x < usLen; ++x) ids[us[x]] = x;
vector<int> ps(usLen, -1);
for (int x = 1; x < usLen; ++x) ps[x] = ids[lca(us[x - 1], us[x])];
return make_pair(us, ps);
}
};
////////////////////////////////////////////////////////////////////////////////
constexpr Mint S = 19901991;
int N, Q;
vector<int> Z;
vector<int> A, B;
vector<int> O, L, R, T;
Hld hld;
namespace brute {
vector<Mint> run() {
cerr<<"[brute::run]"<<endl;
vector<Mint> anss;
vector<int> ws(N, 0);
for (int q = 0; q < Q; ++q) {
if (O[q] == 1) {
vector<int> dp(N, 0);
for (int u = L[q]; u < R[q]; ++u) {
dp[u] = 1;
}
for (int j = N; --j >= 0; ) {
const int u = hld.sid[j];
if (dp[u]) {
++ws[u];
}
if (dp[u] == R[q] - L[q]) {
break;
}
dp[hld.par[u]] += dp[u];
}
} else {
// cerr<<"ws = "<<ws<<endl;
Mint ans = 0;
for (int u = L[q]; u < R[q]; ++u) {
ans += S.pow((Int)Z[__gcd(u + 1, T[q])] * ws[u]);
}
anss.push_back(ans);
}
}
return anss;
}
} // brute
int main() {
for (; ~scanf("%d%d", &N, &Q); ) {
Z.assign(N + 1, 0);
for (int x = 1; x <= N; ++x) {
scanf("%d", &Z[x]);
}
A.resize(N - 1);
B.resize(N - 1);
for (int i = 0; i < N - 1; ++i) {
scanf("%d%d", &A[i], &B[i]);
--A[i];
--B[i];
}
O.resize(Q);
L.resize(Q);
R.resize(Q);
T.assign(Q, 0);
for (int q = 0; q < Q; ++q) {
scanf("%d%d%d", &O[q], &L[q], &R[q]);
--L[q];
if (O[q] == 2) {
scanf("%d", &T[q]);
}
}
hld = Hld(N);
for (int i = 0; i < N - 1; ++i) {
hld.ae(A[i], B[i]);
}
hld.build(0);
// cerr<<hld<<endl;
vector<Mint> anss;
{
anss = brute::run();
}
for (const Mint ans : anss) {
printf("%u\n", ans.x);
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 28ms
memory: 3992kb
input:
998 1000 955556485 952505211 899166521 258704448 894183248 636280051 62949347 983956660 113872828 588367167 208142006 665025449 944228063 284736189 169202015 56096447 404419923 30158095 111191865 717455344 790159420 391379127 208279658 426780799 886604643 940903663 618716147 773652834 385881251 1593...
output:
16521790 13341944 16841705 2220375 880451 3621051 12662029 6300750 3240463 2400556 6501168 3580517 9221391 8381420 12982211 8001004 9361122 17262479 3600913 10401408 16202143 15022309 16341874 7861442 1560390 8340899 12421304 13961591 10421679 12101636 17361912 11781615 4780673 13641787 20102392 171...
result:
ok 490 lines
Test #2:
score: 0
Accepted
time: 29ms
memory: 3924kb
input:
1000 997 103470799 773962597 977631665 55926526 616833039 263471628 825848455 638144717 340710593 68036397 623497249 808915869 345157828 256095693 400262335 173843004 238983751 646376872 243739767 221162275 465477137 772061029 840064611 274062983 522264159 689460088 20129595 287189331 622217799 6948...
output:
13621441 17282360 11241382 15841876 17222347 1880319 12441746 10381083 18222171 7341024 10081427 2900456 2900406 13801602 17521768 19901997 8521022 13281468 2400503 17201967 19942477 14461494 19742168 14461471 12121799 2600806 18902095 1941004 19901993 10221200 8901579 9201080 19442423 720422 130019...
result:
ok 527 lines
Test #3:
score: 0
Accepted
time: 25ms
memory: 3936kb
input:
1000 1000 1697351 841785432 606301324 899151762 398181773 419939453 419455373 826820357 965555426 240847697 718049384 378823565 364137136 867089279 445499605 934770217 134914678 642584637 766848023 203338778 153291975 240768524 446186401 462123008 408740063 755064293 274502953 646610365 27815415 164...
output:
368 198 7021295 16001721 18602311 8021119 17201976 1380573 13141934 3580444 14641604 16681966 3240524 16182225 7541265 8520964 6341385 18922654 17861873 13781440 11581327 14342249 3600640 6821000 16841702 860350 16501686 3420674 18881910 6161028 17022054 3920543 4600572 6300810 3761005 11401360 8181...
result:
ok 502 lines
Subtask #2:
score: 0
Time Limit Exceeded
Test #4:
score: 0
Time Limit Exceeded
input:
65531 65535 968854923 932574892 192297572 866236747 654755663 148562561 273214896 947434573 938626677 992982166 219888853 229840279 676071061 383387319 372883953 729287797 601010887 31942080 990584163 823724544 181337075 918252129 896876911 768539961 357780649 890577681 819641335 320266037 55445939 ...
output:
result:
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%