求助

学术版

喵仔牛奶 @ 2023-02-21 21:16:18

给定 n,m 和一个序列 \{a_{n}\}，满足不存在 (i,j) 使得 a_i<a_j\land a_i\nmid a_j，你需要求出 n 元一次方程

a_1x_1+a_2x_2+a_3x_3+\cdots+a_nx_n=m

的非负整数解的个数。

有没有比 \mathcal{O}(nm) 好的做法？（m\geq n）

by Lynkcat @ 2023-02-21 22:09:23

首先可以做 O(m\log^2 m)。

by Lynkcat @ 2023-02-21 22:11:40

@Lynkcat 大概就是本质不同的数只有 O(\log m) 个然后你直接每次转移暴力卷积

by Lynkcat @ 2023-02-21 22:25:47

@喵仔牛奶 a一定是非负整数吗

by Lynkcat @ 2023-02-21 22:49:00

@Lynkcat 噢倒着卷是 O(m\log m) 的。

by Fido_Puppy @ 2023-02-22 07:19:38

@喵仔牛奶 可以看一下 P4389 付公主的背包，里面的做法是 \Theta(m \log m) 的。

by Fido_Puppy @ 2023-02-22 07:22:41

但是似乎没有用到你的条件。

by 喵仔牛奶 @ 2023-02-22 13:16:21

好吧，有没有什么时间复杂度里面没有 m 的做法qwq（如 \mathcal{O}(n^{1145}\log m)）

by 喵仔牛奶 @ 2023-02-22 13:16:41

|