[問題案] Subset Convolution

[yosupo06]

問題ID: Subset Convolution 問題名: subset_convolution

問題概要

長さ2^Nの配列a_i, b_jが与えられる。

配列 ck = \sum{(i | j == k) && (i & j == 0)} a_i * b_j を求めよ

参考: Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. 2007. Fourier meets möbius: fast subset convolution. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing (STOC ’07). Association for Computing Machinery, New York, NY, USA, 67–74. / arxiv: https://arxiv.org/abs/cs/0611101 参考(日本語解説): Yoichi Iwata 指数時間アルゴリズム入門 (https://www.slideshare.net/wata_orz/ss-12131479)

入力

N
a_0 a_1 ... a_{2^N - 1}
b_0 b_1 ... b_{2^N - 1}

出力

c_0 c_1 ... c_{2^N - 1}

制約

N <= 20?

[yosupo06]

O(N^2 2^N)とO(3^N)の速度差がつくのかは不明

[yosupo06]

値の範囲を制限すればlong longにおさまるが、mod 998244353の方が良さおう

[yosupo06]

https://judge.yosupo.jp/submission/4980 オーバーフローしうるがランダムだと期待値的にオーバーフローしない

[golikov-nik]

https://judge.yosupo.jp/submission/10826 My naive O(3^n) solution passed in 9.8 seconds, maybe you should consider tightening restrictions a bit?

[yosupo06]

In this judge, we put weight to verify our library rather than to drop slow solution. So we set long time limit basically(and to be honest, ideally I want set TL = Infinity).

I think it is okey to keep your solution as fast O(3^n) solution, not TLE solution.

Thanks for your contribution(maybe you are first contributer from non japanese community)!