Atcoder abc230

發表於 更新於 分類於 ， Disqus： 文章字數： 4.4k 所需閱讀時間 ≈ 15 分鐘
G(Möbius函数)H(生成函数,分治卷积)

https://atcoder.jp/contests/abc230/tasks

G - GCD Permutation

给一个1~N的排列p

问有多少个有序对 (i,j), (i<=j), 满足 gcd(i,j) != 1, gcd(p[i],p[j]) != 1

范围

n 2e5

5s

1024mb

我的思路

有点想暴力 然后证明复杂度?

对于 (i,Pi), 取两个中较小的一个, 找所有包含它下标的, 用较大的去验证gcd

最多有6个不同质数因子, 最坏情况 1/2+1/3+1/5+1/7+1/11+1/13 = 1.3左右

所以最坏情况是 找n个坐标

先写个代码再说

https://atcoder.jp/contests/abc230/submissions/34500571

显然 有很多是2 的倍数的,它们如果每个都会去访问n/2, 那么已经就是n^2了, 肯定会超时

想法就是 如果 (2的倍数,3的倍数) 之类做容斥? 但是我容斥完全不会

题解

$\tilde{\mu}(n)= 1,-1,0$

1: 当n为奇数个不同的质数乘积

-1: 当n为偶数个不同的质数乘积

0: 其它

相当于 Möbius函数 取相反数,且 $\mu(1) = 0$

那么满足 $\sum_{d|n} \tilde{\mu}(d)=
\begin{cases}
0 & (\text{if }n=1) \\
1 & (\text{if }n\geq 2)
\end{cases}$

这和Möbius函数 很像, 和= 1-Möbius的和

定义函数

$f(a,b;i,j) = 1/0$, 表示 i,j是a的倍数且 pi,pj 是b的倍数

对于和$S=\sum_{1\leq i\leq j\leq N} \sum_{a=1}^N \sum_{b=1}^N \tilde{\mu}(a) \tilde{\mu}(b)f(a,b;i,j).$

对于给定的$(i,j)$ 令$g=GCD(i,j),g’=GCD(p_i,p_j)$

考虑右侧f要为1, 那么需要同时a是g的约数,b是g’的约数

$\sum_{1\leq i\leq j\leq N} \sum_{a=1}^N \sum_{b=1}^N \tilde{\mu}(a) \tilde{\mu}(b)f(a,b;i,j) = \sum_{1\leq i\leq j\leq N} \sum_{a|g} \sum_{b|g’} \tilde{\mu}(a) \tilde{\mu}(b)$

$= \sum_{1\leq i\leq j\leq N} \sum_{a|g} \tilde{\mu}(a) \sum_{b|g’} \tilde{\mu}(b)$

所以考虑右侧, 只要g,g’ 同时大于等于2,则为1, 否则为0

$= \sum_{1\leq i\leq j\leq N} (g \ge 2 , g’ \ge 2)$, 这里证明了和原题意等价, 因此S就是要求的答案

令$num(a,b) = (a|i,b|p_i)$ 的个数

对于给定$(a,b)$ 有 $\sum_{1\le i\le j\le N}f(a,b;i,j)=\frac{num(a,b)(num(a,b)+1)}{2}$, 相当于找出所有满足$(a|i,b|p_i)$ 的然后组成顺序对

因此又有$S=\sum_{a=1}^N \sum_{b=1}^N \tilde{\mu}(a) \tilde{\mu}(b)
\frac{num(a,b)(num(a,b)+1)}{2}.$

这样你可以计算S了, 虽然是N^2
但是实际上, 对于a, 因为有$(a|i,b|p_i)$, 所以 b 的可选值很小

附加

讲了一下Möbius function 函数的定义,和约数和的结果, 提到了$\displaystyle\sum_{d|n} \tilde{\mu}(d)=1-\sum_{d|n}\mu(d)$

因此每个都可以被快速计算

正向思路?

其实从上面过程中还是能看见一点

本身是要求 $= \sum_{1\leq i\leq j\leq N} (GCD(i,j) \ge 2 , GCD(p_i,p_j) \ge 2)$

有莫比乌斯函数知识有 $[x = 1] = \sum_{i|x} \mu(i)$, 这里$\mu$是莫比乌斯函数

因此可以变形为

$= \sum_{1\leq i\leq j\leq N} (1-\sum_{t_0|GCD(i,j)} \mu(t_0))\cdot (1-\sum_{t_1|GCD(p_i,p_j)} \mu(t_1))$

$= \sum_{1\leq i\leq j\leq N} 1-(\sum_{1\leq i\leq j\leq N}\sum_{t_0|GCD(i,j)} \mu(t_0) + \sum_{1\leq i\leq j\leq N}\sum_{t_1|GCD(p_i,p_j)} \mu(t_1)) + \sum_{1\leq i\leq j\leq N}\sum_{t_0|GCD(i,j)} \mu(t_0) \sum_{t_1|GCD(p_i,p_j)} \mu(t_1)$

3部分

第一部分就是$i\le j$的个数

第二部分,对于$t_0,t_1$ 分别考虑,都是类似的,找都是$t_0 / t_1$的倍数

第三部分,从$t_0,t_1$ 的角度看, 就是上面所谓的num(a,b) 一样的想法

代码

map 850ms https://atcoder.jp/contests/abc230/submissions/34500944

vector+vis 270ms https://atcoder.jp/contests/abc230/submissions/34500900

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
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
int read(){int r;scanf("%d",&r);return r;} // read

#define N 200000
int p[N+10]; // 读入,排列
bool pr[N+10]; // prime[i] = true/false
int mu[N+10]; // mu, 新定义的mu, mu(1) = 0, mu(i) = -莫比乌斯函数(i), i> 1
std::vector<int>d[N+10]; // d[v] = `v的mu不为0的因子`

int main() {
  int n = read();;
  ll ans = 0;
  rep(i,1,n+1) p[i] = read();
  std::fill(pr+2,pr+n+1,true);
  std::fill(mu+2,mu+n+1,-1);
  rep(i,2,n+1){
    if (pr[i]) {
      mu[i] *= -1;
      for (int j = 2*i; j <= n; j+=i) {
        pr[j] = false;
        mu[j] *= ((j/i)%i) ? -1 :0;
      }
    }
    if (mu[i] != 0) for (int j = i; j <= n; j += i) d[j].push_back(i);
  }
  rep(a,2,n+1) if(mu[a] != 0) { // mu(a) * mu(b) * (num(a,b)(num(a,b)+1))/2
    std::unordered_map<int, ll> b2c; // 对于给定a, 的b2c[b] = num(a,b)
    for (int i = a; i <= n; i += a) for (int b : d[p[i]]) b2c[b]++;// a|i, b|p[i]
    for (auto [b,c]: b2c) ans += mu[a] * mu[b] * (c * (c + 1)) / 2;
  }
  printf("%lld\n",ans);
  return 0;
}

H - Bullion

无限数量的块分别重w1,w2,…,wk, 每个两两不同

无限数量包,重量1

包可以容纳 任意个非空包 和 任意个块

安排一辆卡车, 运载力W,

考虑 w=2..W 的每个情况

你需要 让最终外层包重量为w的打包方案数, 包可以嵌套,不能有空包

物品重量相同视为相同, 包内没有顺序,看成可重集合

输出对于每个w的方案数 mod 998244353

限制

w 2.5e5

8s

1024mb

我的思路

先考虑给定w

那么它的内容重量和=w-1

假设包的部分是重k, 那么剩余直接的块重量和为w-k-1

所以f(w) = sum g(k) h(w-k-1)

g(x) = 多个包裹总重量为x的方案数

h(x) = 多个块总重量为x的方案数

像生成函数, 但不会了

题解

这里也提到了上次的222H

上次讲了些技术向的, 这次讲一些直觉向的

上次写了生成方程, 希望an是它的系数, 但没明白讲, 如何用生成方程统计个数

它这用三种区别

序列 小写字母

生成方程 大写字母

集合 书法体大写字母

简单例子, A每种ai个,每个i元,B卖bj个每个j元

  1. 只从A或只从B买一个,可能的方案

  2. 从A和B买各买一个,可能的方案

更具体

A, 1元的一个,2元的一个

B, 1元的一个,3元的一个

看成两个集合$\mathcal{A} = \lbrace 1, 2 \rbrace ,\mathcal{B} = \lbrace 1^\ast , 3^\ast \rbrace.$

对于 1) 就是 $\mathcal{A} +\mathcal{B} = \lbrace 1, 2 , 1^\ast , 3^\ast \rbrace $

对于 2) 就是 $\mathcal{A} \times \mathcal{B} = \lbrace 1, 2 \rbrace \times \lbrace 1^\ast , 3^\ast \rbrace = \lbrace (1,1^\ast), (1,3^\ast), (2,1^\ast), (2,3^\ast) \rbrace$

这是直接从集合角度的方案

考虑, 用生成方程

$A(x) = \sum_{i} a_i x^i = x^1+x^2 $

$B(x) = \sum_{j} b_j x^j = x^1+x^3 $

对于 1) 也是 $C = A+B$, 幂次对应系数相加

对于 2) 也是 $D = A\times B$, 幂次对应系数 的乘积组成新的 和幂次 的系数

这里也就是 集合的操作 和 生成函数操作之间是对应的

例子2

爬山,每次1步或者2步, 问爬到n步的方案数

设集合$\mathcal{F} $ 表示任意步数的序列

那么有$\mathcal{F} = \lbrace \emptyset \rbrace + \lbrace (1) \rbrace \times \mathcal{F}+ \lbrace (2) \rbrace \times \mathcal{F}$, 表示不走, 第一次走一步以后的所有情况,第一次走两步以后的所有情况

对应的生成方程$F(x) = 1x^0 + F(x)x^1 + F(x)x^2$

提取有$F(x) \frac{1}{1-x-x^2}$

实际上也就是 $F(x) = 1 + x + 2x^2 + 3x^3 + 5x^4 + 8x^5 + \dots$, ( 这里生成方程的转换好像需要点啥知识? 不会)

其实就是系数是fibonacci数列

这里说 生成方程 其实是一个 最小的必要信息容器,

但不要过于依赖, 因为有时问题就算靠生成方程得到了系数表达式, 也难以计算

组合结构与函数组合Combinatorial “structure” and function composition

前面讲了 $+$ 和 $\times$ 的操作, 现在讲build block

要被计数的通常是组合的样子, 可以看成 C(集合) = 方案数

如果能得到C的表达式,那么把要求的传进去就能有答案

然后就是 decompose的想法

例如$SEQ(\mathcal{A})$ 表示 一个包含任意个 元素取自A中 的 序列

$\mathrm{SEQ}(\mathcal{A}) = \mathcal{E} + \mathcal{A} + \mathcal{A} \times \mathcal{A} + \mathcal{A} \times \mathcal{A} \times \mathcal{A} + \dots = \sum_{i=0}^\infty \mathcal{A}^i.$

因此对应的生成方程为

$S(x) = 1 + A(x) + A(x)^2 + \dots = \sum_{i=0}^\infty A(x) = \frac{1}{1 - A(x)}$

例如上面的 爬山 ,就是$\mathcal{A} = \lbrace 1,2 \rbrace, A(x) = x^1+x^2$, 带入也能得到上面的式子

现在考虑另外一个例子

2维,从$(0,0)$出发 每次选择非0,$a,b\ge 0$ 的整值, 做 $(x,y) \to (x+a,x+y)$的移动, 问移动到$(N,N)$的方案数

但如果从结构上去看

对于每一步, 对应的集合是$\mathcal{A} = (\mathcal{E} + \mathcal{H} + \mathcal{H}^2 + \dots) \times (\mathcal{E} + \mathcal{W} + \mathcal{W}^2 + \dots) - \mathcal{E}$, 分别一个表示横向一个纵向走一步,走非0的正整距离

$= \mathrm{SEQ}(\mathcal{H}) \times \mathrm{SEQ}(\mathcal{W}) - \mathcal{E}.$ (这里减的定义就是 加 逆元意义

注意到$\mathcal{H} = \lbrace 1 \rbrace$, 其 对应生成方程$H(x) = x^1$

因此$\mathcal{A}$对应生成方程$A(x,y) = \frac{1}{(1-x)(1-y)} - 1$, 这是每一步的生成方程(如何解读1步的生成方程? 其实和集合对应 就是如果方程展开成非负幂次, 不同加项之间选且只能选一个, 展开后x的幂次与纵向步数相关,y的幂次和横向步数相关, 有一点就是永远不要想去带入x和y什么值 得到A的运算结果, 应该把x,y 看成无法和系数,幂次合并的特殊符号)

而 走任意步的集合是$SEQ(\mathcal{A})$

所以任意步的生成方程是

$F(x,y) = \frac{1}{1-A(x,y)} = \frac{(1-x)(1-y)}{1-2x-2y+2xy}$

要求的就是它的$\lbrack x^Ny^N \rbrack$

技巧是拆掉分子, 分母还原成无穷等比的和, 再套二项式

可重集合的结构

令$MULTISET(\mathcal{A})$ 表示元素都取自$\mathcal{A}$ 的可重集合

$A(x)$ 为原集合的生成方程

那么有可重集合的生成方程为$B(x) = exp \left( \sum_{0 < k} \frac{A(x^k)}{k}\right)$

证明:

考虑问题, 很多球, 重$w$的球有$a_w$种, 同一种球无法区分

考虑选一些球, $b_w$ =重量和为$w$的方案数量

$A,B$分别是$a,b$的生成方程

考虑简单情况, 全部的重量都是1, 那么选一个的生成方程是$a_1x^1$

令$r=a_1$, 表示种数

那么其实选的方案用集合表示是

$\begin{aligned} &(\mathcal{E}+\mathcal{C}_ 1+\mathcal{C}_ 1^2 + \dots) \times (\mathcal{E}+\mathcal{C}_ 2+\mathcal{C}_ 2^2 + \dots) \dots \times (\mathcal{E}+\mathcal{C}_ r+\mathcal{C}_ r^2 + \dots) =\prod_ { i=1 }^r \sum_ {j=0}^\infty \mathcal{C}_ i^j.\end{aligned}$

上面求过$SEQ$了, 这里每个集合也只包含$1$,所以生成方程为

$ \frac{1}{(1-x)^r} = \sum_{i=0}^\infty \binom{r + i - 1}{r - 1} x^i.$

对于全部重量是$k$的不同种球,有$a_k$个

其集合结构为$\mathcal{B} = \prod \left( \sum_{i=0}^\infty \mathcal{D}_k \right)^{a_k}.$

而这与上面全是1的区别在于 集合的元素是$k$, 上面的是$1$, 因此区别只是生成方程上面的$x^1$, 现在$x^k$

因此显然生成方程为 $ B(x) = \prod \left(\frac{1}{1-x^k}\right)^{a_k}.$

那么对于不同重量之间的选择是互不影响的, 因此从结构上乘起来

$\mathcal{B} = \prod_{0 \lt k} \left( \sum_{i=0}^\infty \mathcal{D}_k \right)^{a_k}.$

同样的生成方程为 $ B(x) = \prod_{0 \lt k} \left(\frac{1}{1-x^k}\right)^{a_k}.$

最后就是$exp$ 和 $log$

$B(x) = \exp \log B(x) $ 注: a=e^ln(a)

$= \exp \sum_{0 \lt k} -a_k \log (1 - x^k)$ 注: ln(prod(a^i)) = sum i ln(a)

$= \exp \sum_{0 \lt k} a_k \sum_{0 \lt i} \frac{x^{ik}}{i}$ 幂级展开 ln(1-x) = - sum x^i/i

$= \exp \sum_{0 \lt i} \frac{1}{i} \sum_{0 \lt k} a_k (x^i)^k$ 交换sum顺序

$= \exp \left(\sum_{0 \lt i} \frac{A(x^i)}{i} \right)$ 根据A的生成函数

因此多重集合 与 原集合的生成函数关系得证

这里还给了一个用 Pólya’s enumeration theorem 证明的办法 orz 见原文

有一点问题是 exp 在实际得到后如何计算呢

回到题目

定义集合符号

非空包 $\mathcal{F}$

一个块 $\mathcal{G}$

一个包 $\mathcal{B}$

一个空 $\mathcal{E}$

那么显然关系是

$\mathcal{F} = \mathcal{B} \times (MULTISET(\mathcal{F}+\mathcal{G}) - \mathcal{E})$

考虑它们4个的生成函数

显然$F(x)$ 也是答案序列的生成函数

$G(x) = \sum_{1 \leq i \leq K} x^{w_i} $ 表示块,把重量相同 但是种类不同的通过系数加起来

边界 $\lbrace x^0 \rbrace F(x) = \lbrace x^1 \rbrace F(x) = 0$

剩下两个显然 $B(x) = x$, $E(x) = 1$

令$H = F+G$

$F(x) = x \left( \exp \left(\sum_{0 \lt k} \frac{H(x^k)}{k} \right) - 1\right)$

接下来是算了

微分后同时乘x 有

$xF’(x) = F(x) + (F(x) + x) \sum_{0 \lt k} x^{k} H’(x^k).$

这正好是之前不知道如何处理exp, 现在看来, 通过微分/积分 的形式 再创建出 同样表达式,再用F(x)替换掉即可

令$J(x) = \sum_{0 \lt k} x^{k} H’(x^k)$

考虑n次项系数$(n \ge 2)$

$nf_n = f_n+\sum_{0 < k < n} f_k j_{n-k} + j_{n-1}$

移项得到递推表达式

$f_n = \frac{1}{n - 1} \left(j_{n-1} + \sum_{0 \lt k \lt n} f_k j_{n-k}\right)$

对于边界$f_0 = f_1 = j_0 = 0$

$j_n = \lbrack x^n \rbrack \sum_{0 \lt k} x^{k} H’(x^k)$

$= \lbrack x^n \rbrack \sum_{0 \lt k} x^{k} H’(x^k)$

$= \lbrack x^n \rbrack \sum_{0 \lt k} x^{k} \sum_{i=0} (i+1) h_{i+1} (x^k)^i$

$= \sum_{k | n} \lbrack x^n \rbrack \sum_{i=1} i h_{i} (x^k)^i$

$= \sum_{k | n} \frac{n}{k} h_{\frac{n}{k}}$

$= \sum_{d | n} d h_d $

$= \sum_{d | n} d \cdot (f_d + j_d) $

如果$f$知道, 那么$j$ 能快速计算

而f这 很显示需要 分治FFT了

代码

https://atcoder.jp/contests/abc230/submissions/34519255

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
#include <bits/stdc++.h>
#include "atcoder/convolution.hpp"
#include "atcoder/modint.hpp"
using mint = atcoder::modint998244353;
#define MOD 998244353
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
int read(){int r;scanf("%d",&r);return r;} // read
int SZ;
mint inv[500010] = {0,1};
std::vector<mint> f, g, j;
// 提取数组一段 [L..R)
std::vector<mint> get(std::vector<mint>& v, int L, int R) {return {v.begin() + L, v.begin() + R};}

// f[n] = 1/(n-1) (j[n-1] + f * j), fft f * j
void dc(int l, int r) { // 对于f做分治 fft, 每次调用前内部贡献都来自于[0..l),每次只完成[l..r)的计算,不在此函数中对[r,..)产生贡献, 每次先[l..mid) 再 [mid..r), 对于j做简单分治
  if (l + 1 == r) {
    if (l >= 2) f[l] = (f[l] + j[l-1]) * inv[l-1]; // 处理之前 一直是由比它小的贡献 f * j
    if (l >= 1) for (int i = l; i < SZ; i += l) j[i] += (f[l] + g[l]) * l; // j[n] = sum d|n, d * (f[d] + g[d])
    return;
  }
  int mid = (l + r) / 2;
  dc(l, mid); // [0..mid) 都完成了, 把它们贡献散布到[mid, r)
  if (l == 0) { // 注意不要算重了
    auto fj = atcoder::convolution(get(f, 0, mid), get(j, 0, mid));
    rep(i,mid,r) f[i] += fj[i];
  } else {
    auto fj1 = atcoder::convolution(get(f, l, mid), get(j, 0, r - l)); // 两段必定不重复
    auto fj2 = atcoder::convolution(get(f, 0, r - l), get(j, l, mid));
    rep(i,mid,r) f[i] += fj1[i - l] + fj2[i - l];
  }
  dc(mid, r);
}

int main() {
  int W = read(); // 求 [2..W]
  int K = read();
  SZ = 1; // >= n+1, 方便分治 不会重复计算
  while (SZ <= W) SZ *= 2;
  rep(i,2,SZ) inv[i] = (MOD-MOD/i) * inv[MOD%i];
  f = std::vector<mint>(SZ,0);
  g = std::vector<mint>(SZ,0);
  j = std::vector<mint>(SZ,0);
  while(K--) g[read()] += 1; // g[n] = count(val == n)
  dc(0, SZ); // 分治fft
  rep(i,2,W+1) printf("%d\n", f[i].val());
}

总结

G

感觉还是莫比乌斯反演相关的知识点

这个S的定义 感觉凭空出现啊, 这题解有一点搞

但如果不知道这种定义, 还是可以从莫比乌斯函数推导出的

H

不会啊

虽然之前几场的生成函数题目学了, 但是都是说从最简单的选项,建立函数或方程, 然后运算,化简,提取系数

这里通过集合和函数的关系, 感觉学了一点新的东西, 也就是 可以把一个集合操作变成另一个集合, 与 生成方程对应, 换句话说, 生成方程对应了操作,而操作对象是集合就好了, 这样一定程度上有”模块化”和”函数化”的感觉

这个感觉和上次 列生成函数一样还有个好处,就是当结构不再只是层级的,而是会有可相互递归时, 集合就更直观感受

以及exp消除这里办法是微分/积分 同表达式 替换

求解系数,没有直接表达式时, 用递推关系式+分治

然后实现上之前213H也做了分治fft,但是自己依赖自己, 这里的话依赖两个, 要注意分治时不要重复计算, 所以一个办法是把长度做成2的幂次

TODO Pólya’s enumeration theorem

参考

官方题解

之前写的莫反笔记

莫反 CF 548 Div2 D

莫反NowCoder 8282 D

222H 生成函数