求助数论题（poly？）题

学术版

Register_int @ 2022-08-28 08:39:23

$$\sum^n_{i=1}\sum^m_{j=1}\text{Bell}_{\gcd(i,j)}\bmod998244353$$ $\text{Bell}_n$ 为贝尔数，定义见[此](https://oi-wiki.org/math/combinatorics/bell/)。

by fzj2007 @ 2022-08-28 08:40:12

@Register_int 这不就昨天 51nod 的题吗？

by Register_int @ 2022-08-28 08:41:46

@fzj2007 是

by fzj2007 @ 2022-08-28 08:46:54

@Register_int 用 这里 第 5 篇题解的 f 式子化简后面的 \gcd，然后可以转化为

\sum_{i=1}^{\min(n,m)} \lfloor\frac{n}{i}\rfloor \lfloor\frac{m}{i}\rfloor \sum_{d|i}\text{Bell}_d\times \mu(\frac{i}{d})

然后前面的可以整除分块，后面的预处理 \text{Bell} 然后调和级数枚举预处理即可。时间复杂度 \mathcal{O}(n \log n+T \sqrt n)

by bamboo12345 @ 2022-08-28 08:47:50

怎么又重发了个帖子？

by Register_int @ 2022-08-28 08:48:35

@fzj2007 可是怎么预处理 \text{bell}

by Register_int @ 2022-08-28 08:50:39

@bamboo123 因为有些人连 Bell 数是啥都不知道就来这里瞎发板子

by fzj2007 @ 2022-08-28 08:50:58

@Register_int link

by Remake_ @ 2022-08-28 08:51:30

题库搜 集合划分计数

@Register_int

by fzj2007 @ 2022-08-28 08:51:59

如果您学过斯特林数这个东西应该不是很难理解（

by Register_int @ 2022-08-28 08:52:55

@fzj2007 @lstqwq 感谢各位大佬/bx/bx/bx

| 下一页