SemiMultiple
TCO13 Wildcard Round · 2013-02-19 · by snuke
Problem Statement
You are given two
In this problem we will consider N-bit integers. These are nonnegative integers that have at most N bits when expressed in base 2. We will allow leading zeros and treat each such integer as a sequence of exactly N bits.
An N-bit integer is called a semi-multiple of M if it satisfies the following conditions:
- It is not a multiple of M.
- We can change it into a multiple of M by flipping one of its N bits.
Count all N-bit integers that are semi-multiples of M. Return this count modulo 1,000,000,007.
Constraints
- N will be between 1 and 2000, inclusive.
- M will be between 1 and 2000, inclusive.
3 3 Returns: 4
In this case, the N-bit integers are the numbers 0 through 7. Numbers 0, 3, and 6 are multiples of M. Numbers 1, 2, 4, and 7 are semi-multiples of M. For example, 4 written in base 2 is "100" and we can change this either to "000" or to "110" by flipping a single bit. Number 5 is not a semi-multiple of M. Flipping a single bit from "101" produces "001", "111", or "100", and neither of these numbers is divisible by M.
2000 1 Returns: 0
Here, all N-bit integers are multiples of M.
5 2 Returns: 16
Only the least significant bit matters. All odd numbers are semi-multiples of M.
4 6 Returns: 7
3 7 Returns: 6
Submissions are judged against all 116 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SemiMultiple with a public method int count(int N, int M) · 116 test cases · 2 s / 256 MB per case