A.

$p$ 最少要对一个人用。

也就是可以用小于等于 $n-1$ 个位置替换成小于等于 $p$ 的代价，贪心即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void solve() {
  int n, p;
  cin >> n >> p;
  vc<pii> a(n);
  rep(i, n) cin >> a[i].fi;
  rep(i, n) cin >> a[i].se;
  sort(all(a), [&](auto x, auto y) {
    return x.se < y.se;
  });
  ll ans = 1ll * n * p;
  int rem = n - 1;
  for (auto [x, y] : a) {
    if (y < p) {
      ans -= 1ll * min(rem, x) * (p - y);
      rem = max(0, rem - x);
    }
  }
  cout << ans << "\n";
}

B.

令 $mx_{i}$ 为 $\max_{i|j} a_j$，这是选 $i$ 之后的最小代价。

然后将 $mx_i$ 排序，钦定 $mx_i$ 为最大元素，方案数显然是 $2^i$，因为 $i$ 必选。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
const int N = 1e5 + 5;
int a[N], mx[N];
const int P = 998244353;
void solve() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= n; i++) {
    for (int j = i; j <= n; j += i) {
      cmax(mx[i], a[j]);
    }
  }
  vi t;
  for (int i = 1; i <= n; i++) {
    t.pb(mx[i]);
  }
  debug(t);
  int bin = 1;
  int ans = 0;
  sort(all(t));
  for (int i = 0; i < n; i++) {
    ans += 1ll * bin * t[i] % P;
    if (ans >= P) {
      ans -= P;
    }
    bin = (bin * 2) % P;
  }
  cout << ans << "\n";
}

C.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
void solve() {
  int n;
  cin >> n;
  vi a(n), deg(n), vis(n), ban(n), ok(n);
  rep(i, n) cin >> a[i], --a[i];
  queue<int> q;
  vc<vi> g(n);
  rep(i, n) g[i].pb(a[i]), deg[a[i]] += 1;
  rep(i, n) if (deg[i] == 0) { q.emplace(i); }
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    if (vis[u]) {
      continue;
    }
    vis[u] = 1;
    int v = a[u];
    {
      debug(u, v);
      if (!ban[u]) {
        ok[u] = ban[v] = 1;
        q.emplace(v);
      }
      if (--deg[v] == 0) {
        q.emplace(v);
      }
    }
  }
  bool ok2 = true;
  rep(i, n) {
    if (!vis[i]) {
      int cnt = 1;
      for (int j = a[i]; j != i; j = a[j]) {
        cnt += 1;
      }
      if (cnt % 2 == 0) {
        int c = 1;
        vis[i] = 0;
        for (int j = a[i]; j != i; j = a[j]) {
          if (c) {
            ok[j] = 1;
          }
          vis[j] = 1;
          c ^= 1;
        }
      } else {
        ok2 = false;
        break;
      }
    }
  }
  if (!ok2) {
    cout << -1 << "\n";
    return;
  }
  int cnt = 0;
  rep(i, n) if (ok[i]) cnt += 1;
  cout << cnt << "\n";
  rep(i, n) if (ok[i]) { cout << a[i] + 1 << " \n"[i + 1 == n]; }
}

D.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 7, p = 998244353;
unsigned long long E[N], op[N];
int n, f[N], g[N], f1[N], f2[N], F[N];
int h(int u) {
  if (F[u] == u)
    return u;
  return F[u] = h(F[u]);
}
int main() {
  cin >> n;
  int ans = (p + 1) / 2, res = (p + 1) / 2;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &f[i]), g[f[i]]++;
    if (g[f[i]] == 1)
      ans = ans * 2 % p;
    if (g[f[i]] % 2 == 0)
      f1[++f1[0]] = f[i];
    else
      f2[++f2[0]] = f[i];
  }
  if (f1[0] != f2[0])
    res = 0;
  for (int i = 1; i <= f1[0]; i++)
    if (f1[i] != f2[i])
      res = 0;
  for (int i = 1; i <= 200000; i++)
    F[i] = i,
    E[i] = 1ull * rand() * rand() * rand() * rand() * rand() * rand() * rand();
  for (int i = n; i >= 1; i--)
    op[i] ^= E[f[i]];
  for (int i = 1; i <= n; i++)
    op[i] ^= op[i - 1];
  int pos = 0;
  memset(g, 0, sizeof(g));
  for (int i = 1; i <= n; i++) {
    if (op[i] == 0) {
      int C = 0;
      for (int j = pos + 1; j <= i; j++) {
        g[f[j]]++;
        if (g[f[j]] == 1) {
          if (C > 0)
            F[h(C)] = h(f[j]);
          C = f[j];
        }
      }
      for (int j = pos + 1; j <= i; j++) {
        g[f[j]]--;
      }
      pos = i;
    }
  }
  for (int i = 1; i <= n; i++)
    g[f[i]]++;
  for (int i = 1; i <= 200000; i++)
    if (g[i] && h(i) == i)
      res = res * 2 % p;
  cout << (ans - res + p) % p << endl;
  return 0;
}
// 1 1 2 2 1 2 1 2