Hatena::Grouptopcoder

(iwi) { 反省します

TopCoder: [[iwi]] / Twitter: @iwiwi

 | 

2012-04-22

高速ゼータ変換

12:27 | 高速ゼータ変換 - (iwi) { 反省します を含むブックマーク はてなブックマーク - 高速ゼータ変換 - (iwi) { 反省します 高速ゼータ変換 - (iwi) { 反省します のブックマークコメント

例えば,集合に対する関数 f(S) があって,全集合 S に対して g(S) := \sum_{S \subseteq T} f(T) を求めたいとする.

それは,以下の超シンプルなコードで O(n 2^n) でできる.

  rep (i, n) rep (b, 1 << n) if (0 == (b & (1 << i))) a[b] += a[b | (1 << i)];

これは,DP をしている.dp[i][S] := i までの要素に関しては自由度を加味して移行はピッタリになってるやつの和,みたいな感じ.

岩田のスライドの図を見るとわかるかもしれないがコードこれだけなんだからコードも書いといてよと思った.


TCO11 R2A 1000 で使った.むずかった.

AnitaAnita2012/07/10 01:53I thought finding this would be so aurdous but it's a breeze!

olwjnjztlzolwjnjztlz2012/07/10 15:58JLvAv0 <a href="http://gmzyltkanlgy.com/">gmzyltkanlgy</a>

tgpkejttgpkejt2012/07/10 21:55KPsjTC , [url=http://lvjqedojodqw.com/]lvjqedojodqw[/url], [link=http://scogmhbnorom.com/]scogmhbnorom[/link], http://ohjmamgjfpvy.com/

qpomrlgyxqpomrlgyx2012/07/12 12:14hS4OJD <a href="http://jgzisgcvklyh.com/">jgzisgcvklyh</a>

 |