시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 0 | 0 | 0 | 0.000% |
Let's call a number digidivisible in base $B$, if it is divisible by all digits in its base $B$ representation. For example, $728_{10}$ is divisible by $7$, $2$ and $8$, so it is digidivisible in base $10$, and number $264_8 = 180_{10}$ is divisible by $2$, $6$ and $4$, so it is digidivisible in base $8$.
You are given integers $B$ and $n$, and some set of allowed digits from $1$ to $B-1$. Find the number of digidivisible numbers consisting of $n$ digits in base $B$, only containing these allowed digits. Solve this problem for some fixed $n$ and $B$ and for multiple sets of allowed digits.
The first line contains two integers $B$ and $n$ ($2 \le B \le 10$; $1 \le n \le 10^9$). The second line contains an integer $t$ ($1 \le t \le 2^{B-1} - 1$) --- the number of sets of allowed digits you need to solve this problem for.
Then, $t$ lines follow, $i$-th line contains a single string $s_i$, consisting of $B$ zeros and ones. If $s_{i,k} = 1$ (indices begin with 0), then digit $k$ is allowed, otherwise digit $k$ is forbidden. Each set has at least one allowed digit, and digit $0$ is always forbidden. All $t$ sets are distinct.
For each one of the $t$ sets print the answer in a separate line. Because the result might be huge, print it modulo $999\;999\;001$.
번호 | 배점 | 제한 |
---|---|---|
1 | 8 | $B = 10$, $n \le 5$, $t = 1$, all digits except $0$ are allowed |
2 | 9 | $B \le 10$, $B^n \le 10^5$, $t = 1$ |
3 | 9 | $B \le 10$, $B^n \le 10^5$ |
4 | 32 | $B \le 10$, $n \le 50$ |
5 | 13 | $B \le 6$, $n \le 10^9$ |
6 | 14 | $B \le 8$, $n \le 10^9$ |
7 | 15 | $B \le 10$, $n \le 10^9$ |
10 3 2 0111111111 0010101010
56 17
Total number of 3-digit digidivisible numbers in base 10 is $56$. If we only allow even digits, then there are 17 numbers left: 222, 224, 244, 248, 264, 288, 424, 444, 448, 488, 624, 648, 666, 824, 848, 864, 888.