题解 P6381 【『MdOI R2』Odyssey】

· · 题解

【dp】【P6381】『MdOI R2』Odyssey

Analysis

这里有一个比较暴力不需要分析性质的做法。

首先对 w 分解质因数并把指数对 k 取模，把结果 hash 一下，并记录与其配对的数字的 hash 值。然后套路的进行 DAG 上 dp，用 map 存一下状态即可。

设 f_{u, i} 是以 u 为起点，第一条边的 hash 值为 i 的最长路，转移为

f_{u, i} = \max\{f_{v, pi} + l\}

其中 pi 是与 i 配对的 hash 值，v 是从 u 出发的 hash 为 i 的边指向的所有节点，l 是对应边的长度。

时间复杂度 O(m \log w + m \log m + w)。

Code

写起来有点码农，为了防止被卡用了双模数 hash。

namespace Fusu {

const int maxn = 200005;
const int INF = 2000000005;

void Init();
void Calc();
void GetPrime();
void Topo_sort();
void Make_hash();

void Main() {
  Init();
  GetPrime();
  Topo_sort();
  Make_hash();
  Calc();
}

int n, m, t;
int ind[maxn];
struct Edge {
  int v, w, l, nxt;
};
Edge edge[maxn];
int hd[maxn];
int ecnt;
inline void cont(const int u, const int v, const int w, const int l) {
  auto &e = edge[++ecnt];
  e.v = v; e.w = w; e.l = l; e.nxt = hd[u];
  hd[u] = ecnt;
}

void Init() {
  qr(n); qr(m); qr(t);
  for (int i = 1, u, v, w, l; i <= m; ++i) {
    qr(u); qr(v); qr(w); qr(l);
    cont(u, v, w, l);
    ++ind[v];
  }
}

std::queue<int> Q;
int top;
int topo[maxn];
void Topo_sort() {
  for (int i = 1; i <= n; ++i) if (ind[i] == 0) {
    Q.push(i);
  }
  for (int u, v; !Q.empty(); Q.pop()) {
    topo[++top] = u = Q.front();
    for (int e = hd[u]; e; e = edge[e].nxt) if (--ind[v = edge[e].v] == 0) {
      Q.push(v);
    }
  }
}

int pcnt;
int prm[maxn], pre[maxn];
bool np[maxn];
void GetPrime() {
  const int x = 100000;
  for (int i = 2; i <= x; ++i) {
    if (np[i] == false) {
      prm[++pcnt] = i;
      pre[i] = pcnt;
    }
    for (int j = 1, k = prm[j] * i; j <= pcnt; k = prm[++j] * i) if (k <= x) {
      np[k] = true;
      pre[k] = j;
      if ((i % prm[j]) == 0) break;
    } else {
      break;
    }
  }
}

const int maxh = 2;
const int pmod[] = {998244353, 1000000009};

int dcnt;
std::vector<int> d, cd;
int make_hash(const int x) {
  ll ret = 0;
  for (int i = 0; i < dcnt; ++i) if (cd[i] != 0) {
    (ret += (d[i] ^ 20020924ll) * (cd[i] ^ 20020301ll)) %= pmod[x];
  }
  return ret;
}

int hash[maxh][maxn], ph[maxh][maxn];
void Make_hash() {
  for (int i = 1; i <= m; ++i) {
    d.clear(); cd.clear(); dcnt = 0;
    for (int x = edge[i].w, pp = 0; x != 1; x /= prm[pre[x]]) if (pp == pre[x]) {
      if (++cd[dcnt - 1] == t) cd[dcnt - 1] = 0;
    } else {
      d.push_back(pre[x]);
      cd.push_back(t != 1);
      ++dcnt;
      pp = pre[x];
    }
    for (int j = 0; j < maxh; ++j) {
      hash[j][i] = make_hash(j);
    }
    for (int j = 0; j < dcnt; ++j) if (cd[j]) {
      cd[j] = t - cd[j];
    }
    for (int j = 0; j < maxh; ++j) {
      ph[j][i] = make_hash(j);
    }
  }
}

std::map<std::pair<int, int>, int> f[maxn];
void Calc() {
  std::pair<int, int> k;
  int ans = 0;
  for (int i = n, u = topo[i], v; i; u = topo[--i]) {
    for (int e = hd[u]; e; e = edge[e].nxt) {
      v = edge[e].v;
      k = std::make_pair(hash[0][e], hash[1][e]);
      f[u][k] = std::max(f[u][k], edge[e].l);
      auto j = std::make_pair(ph[0][e], ph[1][e]);
      f[u][k] = std::max(f[u][k], edge[e].l + f[v][j]);
      ans = std::max(ans, f[u][k]);
    }
  }
  qw(ans, '\n');
}

} // namespace Fusu