Маскийн бүх submask-ийг (s − 1) & m аргаар, илүү алхамгүйгээр гаргана.

Advanced & LegendХугацаа: O(2ᵏ), k — m тооны 1 битСанах ой: O(1)

Эхлээд жижиг бодлого

m = 13 буюу 1101. Энд 0, 2, 3-р битүүд 1 байна. Тэдгээрийн заримыг нь л үлдээсэн тоонууд нь submask.

Бүгд 2³ = 8 ширхэг: 13, 12, 9, 8, 5, 4, 1, 0. Программ яг энэ дарааллаар хэвлэнэ.

Энгийн аргаас санаа руу

Энгийн арга: 0-ээс m хүртэлх бүх s-ийг шалгаад (s & m) == s бол хэвлэнэ. m = 13 бол 14 тоо шалгаж 8-ыг нь хэвлэнэ. Том m дээр ихэнх тоо дэмий шалгагдана.

Гол санаа: s = (s - 1) & m. s − 1 нь s-ээс бага хамгийн ойрын тоо. & m нь m-д байхгүй битүүдийг арилгаж, s-ээс бага хамгийн том submask-ийг шууд өгнө. Ингэж нэг ч илүү тоо шалгахгүй.

Нэр томьёо ба тэмдэглэгээ

mask
Олонлогийг тоогоор илэрхийлсэн нь: i-р бит 1 бол i-р зүйл сонгогдсон.
submask
(s & m) == s байх s. m-ийн 1 битүүдийн заримыг нь л үлдээсэн тоо.
(s − 1) & m
s-ээс бага хамгийн том submask.
3ⁿ
n битийн бүх маскийн бүх submask-ийн тоо. Бит бүр 3 төлөвтэй: m-д байхгүй, m-д байгаа ч s-д байхгүй, хоёуланд байгаа.
m = 13
1
3
1
2
0
1
1
0
m = 13
хэвлэсэн
хоосон

m = 13 (1101). m-ийн 1 битүүдээс заримыг нь л үлдээсэн тоог submask гэдэг. m-д 3 ширхэг 1 бит байгаа тул 8 submask бий. Бүгдийг нь томоос нь эхлэн гаргая.

Алхам 1 / 16
Хурд
  • m-ийн 1 бит
  • Хэвлэсэн s
  • Шинэ s
  • & m арилгах бит
  • m-ийн 0 бит
Слайд 1 / 5

Submask гэж юу вэ?

m = 1101 бол 3 зүйл сонгосон олонлог. Тэднээс заримыг нь л авсан тоо бүр submask: 1101, 1100, 1001, 1000, 0101, …, 0000.

submask-enumeration.cpp
#include <bits/stdc++.h>
using namespace std;
int m;
int main() {
cin >> m;
int s = m;
while (s > 0) {
cout << s << ' ';
s = (s - 1) & m;
}
cout << 0 << '\n';
return 0;
}

Юунд хэрэгтэй вэ?

Bitmask DP-д олонлогийн бүх дэд олонлогийг шалгах хэрэг их гардаг. 0-ээс m хүртэлх бүх тоог шалгахын оронд зөвхөн submask-уудаар явна.

Яаж ажилладаг вэ?

1. s = m: хамгийн том submask нь m өөрөө. 2. s-ийг хэвлэнэ, эсвэл ашиглана. 3. s = (s − 1) & m: s − 1 хийхэд хамгийн баруун 1 бит унтарч, түүнээс баруун талын битүүд асна. & m нь m-д байхгүй битүүдийг арилгана. Ингэхэд дараагийн бага submask гарна. 4. s = 0 болтол давтаад, эцэст нь хоосон маск 0-ийг хэвлэнэ. m-д k ширхэг 1 бит байвал яг 2ᵏ алхам. n битийн бүх маскийн бүх submask-аар явбал нийт 3ⁿ алхам. Оролт: m.

Яагаад зөв, хэр хурдан бэ?

s − 1 хийхэд s-ийн хамгийн баруун 1 бит 0 болж, баруун талын бүх бит 1 болно. & m нь эдгээрээс m-д байгааг л үлдээнэ. Үр дүн нь s-ээс бага submask-уудаас хамгийн том нь. Тиймээс бүх submask буурах дарааллаар, нэг ч алгасахгүй гарна.

m-д k ширхэг 1 бит байвал 2ᵏ алхам. n = 15 бол бүх маскийн бүх submask-аар явахад 3¹⁵ ≈ 14 сая алхам. Энэ нь 4¹⁵ ≈ 1 тэрбумаас хамаагүй бага.

Түгээмэл алдаа

  • while (s > 0) нь 0-ийг хэвлэхгүй. Хоосон олонлог хэрэгтэй бол loop-ын дараа тусад нь хий. Энэ код cout << 0 гэж хийдэг.
  • for (s = m; s >= 0; s = (s - 1) & m) гэж бичвэл зогсохгүй: 0-ийн дараа (0 - 1) & m = m болж дахин эхэлнэ.
  • Бүх маскийн submask-аар явах хугацааг 2ⁿ · 2ⁿ гэж буруу бодох. Жинхэнэ тоо нь 3ⁿ.

Хязгаарын тохиолдол

  • m = 0: loop огт эргэхгүй, зөвхөн 0 хэвлэгдэнэ.
  • Ганц бит, жишээ нь m = 8: 8, 0 гэсэн хоёр л submask.
  • Бүх бит 1, жишээ нь m = 15: 0-ээс 15 хүртэлх 16 тоо бүгд submask.

Өөрийгөө шалга

  1. m = 6 бол программ юу хэвлэх вэ?

    Хариу харах

    6 4 2 0.

  2. m = 165 буюу 10100101 хэдэн submask-тай вэ?

    Хариу харах

    16. 1 бит 4 ширхэг тул 2⁴ = 16.

  3. s = 9, m = 13 бол дараагийн s хэд вэ?

    Хариу харах

    8. (9 − 1) & 13 нь 1000 & 1101 = 1000.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.m = 11 (1011) дээр s-ийн дарааллыг гараар бич.

    Hint харах

    Эхлээд s = 11, дараа нь (s − 1) & 11.

    Хариу ба тайлбар

    11 10 9 8 3 2 1 0. 1 бит 3 ширхэг тул 8 submask.

  2. 2.Submask бүрийг хэвлэхийн оронд хэдэн submask-д 0-р бит 1 байгааг тоол.

    Hint харах

    s & 1 нь 0-р битийг өгнө.

    Хариу ба тайлбар

    Loop дотор if (s & 1) cnt++; нэм. m-ийн 0-р бит 1 бол хариу 2ᵏ⁻¹, 0 бол 0. Энд k нь m-ийн 1 битийн тоо.

  3. 3.n ≤ 15 зүйл, mask бүрт w[mask] жин өгөгдөв. Mask бүрийн бүх submask-ийн жингийн нийлбэрийг ол.

    Hint харах

    Mask бүрээр гадна loop, түүний submask-аар дотор loop.

    Хариу ба тайлбар

    for (m = 0; m < (1 << n); m++) for (s = m; ; s = (s - 1) & m) { sum[m] += w[s]; if (s == 0) break; } Нийт 3¹⁵ ≈ 14 сая алхам.

Жишээ

Оролт

13

Гаралт

13 12 9 8 5 4 1 0