Codeforces 1845F Swimmers in the Pool 题解

发表于 分类于

思路

由物理知识可得，两个人 ii 和 jj 的相逢时刻只可能形如 k×2l∣vi±vj∣,k∈N∗\frac{k \times 2l}{|v_i \pm v_j|}, k \in \N^*．题意就是计算这样的有理数数量．

考虑计算出 ∣vi±vj∣|v_i \pm v_j| 的所有可能的值．这是经典问题，若我们设 F(x)=∑ixaiF(x) = \sum_i x^{a_i}，G(x)=∑ix−aiG(x) = \sum_i x^{-a_i}，那么 [xn](F∗G)(x)[x^n](F * G)(x) 就是相减等于 nn 的二元组数量，相加的同理．

记 U={∣vi±vj∣}U = \{|v_i \pm v_j|\}，又由于分子上都有 2l2l，那么问题可以转化为计算形如 x=kw,w∈Ux = \frac{k}{w}, w \in U 且满足 x≤t2lx \le \frac{t}{2l} 的有理数 xx 的数目．对于某个 ww，这样的分数数目显然是 ⌊tw2l⌋\left\lfloor \frac{tw}{2l} \right\rfloor，但直接求和显然会有重复贡献．

考虑如何去掉重复贡献．对于每个 ww，如果我们只计算以其为分母的最简分数数量，记这个数量为 fwf_w，那么计算不同有理数个数时，ww 的每个因数 dd 都会对答案恰好贡献 fdf_d．

考虑 fif_i 的计算．我们需要从不考虑限制的 ⌊ti2l⌋\left\lfloor \frac{ti}{2l} \right\rfloor 个分数中去除非最简分数，而这些非最简分数的最简分数形式的分母肯定是 ii 的一个因数．枚举 ii 的因数并去除这些非最简分数，我们可以得到以下转移：

fi=⌊ti2l⌋−∑d∣ifdf_i = \left\lfloor \frac{ti}{2l} \right\rfloor - \sum_{d | i} f_d

若记 VV 表示 UU 中元素所有因数构成的集合，答案即为 ∑d∈Vfd\sum_{d \in V} f_d．

转移复杂度是调和级数求和级别，计算 UU 使用 NTT 优化卷积即可．时间复杂度 O(nlog⁡n)O(n \log n)．

代码

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <algorithm>
#include <cstdio>

inline int rd() {
  int x = 0, f = 1, c = getchar();
  while (((c - '0') | ('9' - c)) < 0)
    f = c != '-', c = getchar();
  while (((c - '0') | ('9' - c)) > 0)
    x = x * 10 + c - '0', c = getchar();
  return f ? x : -x;
}

using i64 = long long;
const int B = 2e5;
const int N = 1 << 20;
const i64 Mod = 1e9 + 7;

const i64 P = 998244353;
const i64 G = 3;
const i64 iG = 332748118;
i64 fpow(i64 b, i64 p) {
  i64 res = 1;
  for (; p; b = b * b % P, p >>= 1) {
    if (p & 1) res = res * b % P;
  }
  return res;
}
namespace ntt {
  int lim, r[N];
  int init(int n) {
    lim = 1;
    while (lim < n) lim <<= 1;
    for (int i = 0; i < lim; i++) {
      r[i] = (r[i >> 1] >> 1) | ((i & 1) ? lim >> 1 : 0);
    }
    return lim;
  }
  void run(i64 *f, bool inv) {
    for (int i = 0; i < lim; i++) {
      if (i < r[i]) std::swap(f[i], f[r[i]]);
    }
    for (int mid = 1; mid < lim; mid *= 2) {
      i64 wn = fpow(inv ? iG : G, (P - 1) / (mid * 2));
      for (int i = 0; i < lim; i += (mid * 2)) {
        i64 w = 1;
        for (int j = 0; j < mid; j++, w = w * wn % P) {
          i64 a = f[i + j], b = w * f[i + mid + j] % P;
          f[i + j] = (a + b) % P, f[i + mid + j] = (a - b + P) % P;
        }
      }
    }
    if (inv) {
      i64 il = fpow(lim, P - 2);
      for (int i = 0; i < lim; i++) f[i] = f[i] * il % P;
    }
  }
};

i64 l, t, n, a[N];
i64 f[N], g[N];
bool flg[N];
i64 dp[N];

int main() {
  l = rd(), t = rd(), n = rd();
  for (int i = 1; i <= n; i++) a[i] = rd();

  for (int i = 1; i <= B * 2; i++) {
    (dp[i] += ((t * i) / (2 * l)) % Mod) %= Mod;
    for (int j = i + i; j <= B * 2; j += i) {
      (dp[j] += Mod - dp[i]) %= Mod;
    }
  }

  for (int i = 1; i <= n; i++) f[a[i]] = 1;
  for (int i = 1; i <= n; i++) g[-a[i] + B] = 1;
  int lim = ntt::init(B * 2);
  ntt::run(f, 0), ntt::run(g, 0);
  for (int i = 0; i < lim; i++) g[i] = g[i] * f[i] % P;
  for (int i = 0; i < lim; i++) f[i] = f[i] * f[i] % P;
  ntt::run(f, 1), ntt::run(g, 1);
  for (int i = 1; i <= n; i++) f[a[i] + a[i]]--;
  g[B] -= n;
  for (int i = 1; i <= B * 2; i++) {
    if (f[i]) flg[i] = 1;
    if (g[i]) flg[std::abs(i - B)] = 1;
  }
  for (int i = 1; i <= B * 2; i++) {
    for (int j = i + i; j <= B * 2; j += i) {
      flg[i] |= flg[j];
    }
  }

  i64 ans = 0;
  for (int i = 1; i <= B * 2; i++) {
    if (flg[i]) (ans += dp[i]) %= Mod;
  }
  printf("%lld\n", ans);
  return 0;
}

参考

PEKKA_l, CF1845F 题解