QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#260380#7839. 虹hos_lyric#10 29ms3992kbC++1410.6kb2023-11-22 06:21:072024-07-04 03:08:12

Judging History

你现在查看的是最新测评结果

  • [2024-07-04 03:08:12]
  • 评测
  • 测评结果:10
  • 用时:29ms
  • 内存:3992kb
  • [2023-11-22 06:21:07]
  • 提交

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%