关于狄利克雷卷积

学术版

Spasmodic @ 2020-10-11 17:50:55

请问可不可以在低于 O(n\log n) 时间内做：

  1. 任意两个函数的卷积
  2. 积性函数的卷积

by Fading @ 2020-10-11 17:52:13

@happydef 不是有 dlkl 前缀和吗

by Spasmodic @ 2020-10-11 17:52:21

禁止wyy回复

by Spasmodic @ 2020-10-11 17:52:55

@Fading 不行罢 狄利克雷好像只能 1*f？还是有更高级的做法您教教我

by HohleFeuerwerke @ 2020-10-11 17:53:06

  1. 显然 xxs 能做吧

by Spasmodic @ 2020-10-11 17:53:36

啊这我傻逼 好第二个问题不管了

by tiger0134 @ 2020-10-11 17:54:18

2 能不能直接筛啊，1 不会

by HohleFeuerwerke @ 2020-10-11 17:55:59

1 得看吧，要观察性质

by Fading @ 2020-10-11 17:56:19

@happydef 是我菜了吗，不能求一下前缀和 乘一下 再求一下差分吗

by Spasmodic @ 2020-10-11 17:56:32

@HohleFeuerwerke 随机函数，懂？

by Fading @ 2020-10-11 17:56:40

我乱说的，如果不行别喷我

| 下一页