子集卷积 exp/kel

学术版

zhiyangfan @ 2022-02-08 11:38:58

上课讲了，在写博客，发现自己忘了咋求了。是这么个玩意：

g_i=\sum_{i_1,i_2,\cdots,i_k}[|i_1|+|i_2|+\cdots+|i_k|=|i|][i_1\operatorname{or}i_2\operatorname{or}\cdots\operatorname{or}i_k=i]f_{i_1}f_{i_2}\cdots f_{i_k}

怎么在 \mathcal{O}(n^22^n) 的时间复杂度内求解啊

by Aleph1022 @ 2022-02-08 12:53:33

@zhiyangfan 像子集卷积一样 fmt 之后做 2^n 次 \Theta(n^2) 的 \exp 再 ifmt。

by zhiyangfan @ 2022-02-08 13:23:22

@Alpha1022 能具体说一下 2^n 次 \exp 是怎么做的吗

by Aleph1022 @ 2022-02-08 15:47:29

@zhiyangfan 在 fmt 之后不是会变成一维卷积一维点积吗，点积那一维每个值对应的占位多项式 exp

by zhiyangfan @ 2022-02-08 20:08:24

@Alpha1022 为啥不是多项式快速幂呢

by Aleph1022 @ 2022-02-08 20:22:30

@zhiyangfan 不是你说的子集卷积 exp 吗 /kel

by zhiyangfan @ 2022-02-08 20:25:04

@Alpha1022 我刚刚想了一下您说的过程。就是在子集卷积的这个地方：

for (int i = 0; i <= m; ++i)
    for (int j = 0; j <= i; ++j)
        for (int k = 0; k < n; ++k) 
            (c[i][k] += (ll)a[j][k] * b[i - j][k] % mod) %= mod;

固定 k 之后，魔改为：

(g[i][k] += f[i1][k] * f[i2][k] * ... * f[in][k] % mod) %= mod

这个样子。那应该是对 f[k] 对应的形式幂级数做多项式快速幂得到的结果啊

by Aleph1022 @ 2022-02-08 20:31:15

@zhiyangfan 建议先搞清楚 exp 和快速幂的区别（

by zhiyangfan @ 2022-02-08 20:42:57

@Alpha1022 刚刚想错了，但我还是觉得应该是多项式快速幂

f_S+f_S^2+f_S^3+\cdots

只不过可以直接变成多项式求逆，不用 \exp 和 \ln 了。

不过刚刚学长的话感觉没错（

by Aleph1022 @ 2022-02-08 20:56:44

@zhiyangfan ？我不是很懂

by Aleph1022 @ 2022-02-08 20:57:31

@zhiyangfan 那肯定是要经过 fmt 之后的啊（

| 下一页