n4_t https://blog.hatena.ne.jp/n4_t/ naoya_t@hatenablog https://naoyat.hatenablog.jp/ Algorithms memo 個ある何かの0個以上から成る集合をビットの整数で表すことにする。 このとき、集合に含まれる要素が個なら全部でビット立っている 。 （__builtin_popcount(S) == k）この集合の部分集合をすべて列挙しようとすると、空集合も含め通りある。 集合Sとしてありうる全てのパターンについてこれを列挙することを考えると、 個から個選ぶ組み合わせが通りで、そのそれぞれについて通りの部分集合があるので全部で 通りについて考えることになる。ここで驚くべきことは、任意の非負整数について $$ \sum_{k=0}^{n}{_nC_k\cdot2^k}=3^n $$ が成り立つということである。各… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fnaoyat.hatenablog.jp%2Fentry%2Forder-pow-3-n" title="〈説明用メモ〉O(3^N)について本気出して考えてみた - naoya_t@hatenablog" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://chart.apis.google.com/chart?cht=tx&chl=n Hatena Blog https://hatena.blog 2019-01-16 02:37:25 rich https://naoyat.hatenablog.jp/entry/order-pow-3-n 1.0 100%