QOJ #5573. Holiday Regifting 题解

Description

有一个 $n$ 个点的图，有 $m$ 条有向边 $u \to v$，保证 $u<v$，每个点有一个 $c_i$。

一开始每个点有一个点权 $a_i$。每次操作可以给 $1$ 号点的点权加上 $1$。如果一个点的 $a_i = c_i$，那么 $a_i \gets 0$，并且所有 $i$ 指向的点 $j$，都会 $a_j \gets a_j + 1$。求多少次之后所有 $a_i$ 会再一次全变成 $0$。答案模 $998244353$。

$1 \le n \le 10^4,1 \le m \le 3\times 10^4$。

Solution

由于每条边满足 $u<v$，所以每个点 $i$ 的点权只和小于 $i$ 的点有关，考虑从小到大确定答案。

假设枚举到了 $i$，如果 $a_i\neq 0$，则需要让 $<i$ 的点继续操作，直到 $a_i=0$。

由于前面的已经确定了最优方案，所以一定是整体乘一个倍数，然后让 $a_i$ 变成 $0$。

容易发现这个倍数是 $\displaystyle\frac{c_i}{\gcd(a_i,c_i)}$，乘上它并更新更新后面的数即可。

时间复杂度：$O(n^2+nm)$。

Code

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 1e4 + 5, kMod = 998244353;

int n, m;
int c[kMaxN];
int64_t a[kMaxN];
std::vector<int> G[kMaxN];

void dickdreamer() {
  std::cin >> n >> m;
  for (int i = 1; i <= n; ++i) std::cin >> c[i];
  for (int i = 1; i <= m; ++i) {
    int u, v;
    std::cin >> u >> v;
    G[u].emplace_back(v);
  }
  int ans = 1;
  a[1] = 1;
  for (int i = 1; i <= n; ++i) {
    int coef = c[i] / std::__gcd((int)a[i], c[i]);
    ans = 1ll * ans * coef % kMod;
    for (int j = i; j <= n; ++j) a[j] *= coef;
    for (int j = i; j <= n; ++j) {
      for (auto k : G[j]) {
        a[k] += a[j] / c[j];
      }
      a[j] %= c[j];
    }
  }
  std::cout << ans << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}