Interesting World of Arrays
Time limit2sMemory limit512 MB
Count arrays of length n whose values each satisfy a[i] = count(i) mod m, for n up to 12 and m up to 1e9.
- Level
Hard8 of 10
- Topics
- Combinatorics, Math, Brute force, Backtracking
- Solved
- No attempts yet
Problem
Gwen is about to finish her Ph.D. thesis titled The Interesting World of Arrays. She studies many kinds of arrays, but her favorite is the counting array. A counting array counts how many times each possible value appears in an array. Formally, [c0, c1, c2, . . . , cn−1] is the counting array of A = [a0, a1, . . . , an−1] if A contains c0 zeroes, c1 ones, c2 twos, and so on. For example, if A = [4, 1, 2, 0, 2], then its counting array is [1, 1, 2, 0, 1]. A counting array is defined only when ai is an integer with 0 ≤ ai < n for all 0 ≤ i < n.
The last chapter of Gwen's thesis is about mod-m self-describing arrays. Let A = [a0, a1, . . . , an−1] be an array with counting array [c0, c1, . . . , cn−1]. For a positive integer m, the array A is a mod-m self-describing array if ai ≡ ci (mod m) for all 0 ≤ i < n. That is, ai and ci leave the same remainder when divided by m. For example, consider A = [6, 6, 4, 6, 3, 5, 3] and its counting array [0, 0, 0, 2, 1, 1, 3]. The two are the same modulo 2 (both become [0, 0, 0, 0, 1, 1, 1]), so A is a mod-2 self-describing array.
The only thing left before Gwen submits her thesis is to compute the number of mod-m self-describing arrays for various values of n and m. Help her compute these numbers.
Input
The input consists of a single line containing two integers: n (1 ≤ n ≤ 12), the length of the array, and m (2 ≤ m ≤ 109), the modulus.
Output
Display the number of mod-m self-describing arrays of length n.