Bitmask and digit DP

Questions 1 to 5 of 8

1. 1. An AI tool wrote this for 20 items. For each mask, it loops over every submask s of that mask, and it does a constant amount of work per pair. ``cpp for (int mask = 0; mask < (1 << n); mask++) for (int s = mask; ; s = (s - 1) & mask) { total += f[s]; if (s == 0) break; } `` How many (mask, submask) pairs does this visit when n = 20?

   About 2 times 10^7, which is 20 times 2^20About 10^6, which is 2^20, one per maskAbout 3.5 times 10^9, which is 3^20400, which is 20 squared
2. 2. Using the same submask loop, how many (mask, submask) pairs does it visit when n = 18?

   Type a number.

3. 3. Which statements about the tight flag in digit DP are true?

   Pick every answer that is true.

   Once a chosen digit is smaller than N's digit at that position, the flag turns off and stays off for every later positionWhile the flag is on, each digit may be at most N's digit at the same positionA tight state depends on N's digits, so its result may be stored in the memo and reused for other NTurning the flag off after the first digit is safe for every N, because the later digits are then free
4. 4. An AI tool wrote a digit DP to count x from 1 to N = 130 with digit sum divisible by 3 and at most one zero. On this input it prints 330, but the answer is 43. The tight flag is never passed to the next position, so every 3-digit string counts. Which numbers are wrongly counted?

   Numbers above 130, such as 258, which has digit sum 15 and no zeroOnly the numbers with a zero in the middle, such as 105Only the numbers that have a digit sum of exactly 3Numbers with more than 3 digits, which the DP never reads
5. 5. Another AI digit DP pads each number to three digits, so 5 is read as 005. It counts zeros in the padding, and on N = 130 it prints 36 instead of 43. Which change fixes the bug?

   Remove the tight flag, because the padding comes from itStart the zero count at 1 for every number, so the padding is counted onceSubtract the number of digits of N from the final answerKeep a started flag, and do not add to the zero count until a nonzero digit has been written