{"image_url":null,"provider_url":"https://hatena.blog","categories":["\u7af6\u6280\u30d7\u30ed\u30b0\u30e9\u30df\u30f3\u30b0"],"width":"100%","description":"2\u7a2e\u985e\u306e\u7573\u307f\u8fbc\u307f subset convolution \u8cc7\u65991 \u8cc7\u65992 \u8cc7\u65993 \u30bc\u30fc\u30bf\u5909\u63db\u3068\u30e1\u30d3\u30a6\u30b9\u5909\u63db\u306f\u9006\u5909\u63db\u306e\u95a2\u4fc2\u306b\u3042\u308b \u30bc\u30fc\u30bf\u5909\u63db\uff08\u72b6\u614bx\u3092\u542b\u3080\u72b6\u614by\u3092\u5168\u5217\u6319\uff09 \u9ad8\u901f\u30bc\u30fc\u30bf\u5909\u63db\u3067O(n2^n) g[x] = sum{y\u2286x}f(y) \u2192 rep(i, 0, N) rep(msk, 0, 1 g[x] = sum{x\u2286y}f(y) \u2192 rep(i, 0, N) rep(j, 0, 1 \u53c2\u8003 \u9ad8\u901f\u30bc\u30fc\u30bf\u5909\u63db\u306f\u74b0\u3067\u52d5\u304f\uff08+, *, max, gcd\u306a\u3069\uff09 \u30e1\u30d3\u30a6\u30b9\u5909\u63db\uff08\u72b6\u614bx\u306e\u90e8\u5206\u72b6\u614by\u3092\u5168\u5217\u6319\uff09 \u9ad8\u901f\u30e1\u30d3\u30a6\u30b9\u5909\u63db\u3067O(n2^n) g[x] = sum{y\u2286x}(-1)^|x-y| g[y] \u2026","type":"rich","published":"2017-05-20 12:56:07","author_url":"https://blog.hatena.ne.jp/hamayanhamayan/","version":"1.0","provider_name":"Hatena Blog","blog_title":"\u306f\u307e\u3084\u3093\u306f\u307e\u3084\u3093\u306f\u307e\u3084\u3093","title":"\u7af6\u6280\u30d7\u30ed\u30b0\u30e9\u30df\u30f3\u30b0\u306b\u304a\u3051\u308b\u7573\u307f\u8fbc\u307f\u554f\u984c\u307e\u3068\u3081\uff08FFT,\u30a2\u30c0\u30de\u30fc\u30eb\u5909\u63db,\u30e1\u30d3\u30a6\u30b9\u5909\u63db,\u30bc\u30fc\u30bf\u5909\u63db\uff09","url":"https://blog.hamayanhamayan.com/entry/2017/05/20/125607","html":"<iframe src=\"https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.hamayanhamayan.com%2Fentry%2F2017%2F05%2F20%2F125607\" title=\"\u7af6\u6280\u30d7\u30ed\u30b0\u30e9\u30df\u30f3\u30b0\u306b\u304a\u3051\u308b\u7573\u307f\u8fbc\u307f\u554f\u984c\u307e\u3068\u3081\uff08FFT,\u30a2\u30c0\u30de\u30fc\u30eb\u5909\u63db,\u30e1\u30d3\u30a6\u30b9\u5909\u63db,\u30bc\u30fc\u30bf\u5909\u63db\uff09 - \u306f\u307e\u3084\u3093\u306f\u307e\u3084\u3093\u306f\u307e\u3084\u3093\" class=\"embed-card embed-blogcard\" scrolling=\"no\" frameborder=\"0\" style=\"display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;\"></iframe>","blog_url":"https://blog.hamayanhamayan.com/","author_name":"hamayanhamayan","height":"190"}