用n种颜色填长度为m的数组，每种颜色都出现偶数次，可以O(m)算吗

学术版

Larunatrecy @ 2023-03-01 19:34:03

用n种颜色填长度为m的数组，每种颜色都出现偶数次，可以O(m)算吗

by chenguoyi @ 2023-03-01 19:45:22

只会O(mlogm)QAQ。

by 小粉兔 @ 2023-03-01 19:48:03

无非是

\hat F(x) = \sum_{i = 0}^{\infty} [2 \mid i] \frac{x^i}{i!}

然后求 [x^m / m!] \hat F^n

注意 \hat F(x) = (\mathrm{e}^{x} + \mathrm{e}^{-x}) / 2

这样可以 $\mathcal O(n)

by Semsue @ 2023-03-01 19:49:03

@小粉兔 但他不是要 O(m) 吗

by Larunatrecy @ 2023-03-01 19:51:19

@小粉兔 感谢

by 小粉兔 @ 2023-03-01 19:52:23

容斥没出现的颜色反演一下试试？

by 小粉兔 @ 2023-03-01 19:53:03

退役了，原本不高的数数水平越来越低

by zjx331 @ 2023-03-01 19:54:09

《原 本 不 高》 sto 小粉兔

by Aleph1022 @ 2023-03-02 21:36:27

@Larunatrecy 载谭 binomial sum。

by Aleph1022 @ 2023-03-02 21:36:43

@小粉兔 是不是没好好读 ei 博客

by 小粉兔 @ 2023-03-02 22:04:52

@Alpha1022 根本没读懂过啊

| 下一页