Unique Birthday Gift
Your birthday is coming soon and one of your friends, Alex, is thinking about a gift for you. He knows that you really like integer arrays with interesting properties.
He selected two numbers, N and K, and decided to write down on paper all integer arrays of length K (in form a[1], a[2], ..., a[K]), where every number a[i] is in the range from 1 to N, and, moreover, a[i+1] is divisible by a[i] (where 1 < i <= K), and give you this paper as a birthday present.
Alex is very patient, so he managed to do this. Now you're wondering, how many different arrays are written down on this paper?
Since the answer can be really large, print it modulo 10000.
Input: The first line contains an integer n, k. n, denoting the maximum possible value in the arrays. k, denoting the length of the arrays.
Sample cases: Input 2 1 2 2 3 2
Output: 2 The required length is 1, so there are only two possible arrays: [1] and [2]. 3 All possible arrays are [1, 1], [1, 2], [2, 2]. [2, 1] is invalid because 1 is not divisible by2. 5 All possible arrays are [1, 1], [1, 2], [1, 3], [2, 2], [3, 3].
can you tell the constraints of $$$n$$$ and $$$k$$$?
1 =< n =< 100000 1 =< k =< n
so, firstly let get rid of repetition in our array, for example: we won't count array [1, 2, 2, 4] cause 2 appears twice.
let's solve this problem. we can see that every new element will be at least 2 times greater than the previous. so, if $$$n < 10^5$$$, we will place not more than $$$log (n) + 1= 17$$$ elements. let's solve this using dynamic programming: $$$dp_{i, j} = $$$ number of arrays consists of $$$i$$$ elements and last element is $$$j$$$. $$$dp_{i, j}$$$ we update from $$$dp_{i-1, k}$$$ for all $$$k$$$ which are divisors of $$$n$$$ except $$$k = n$$$. so, as $$$i$$$ as small enough (17), it will work very fast.
how this help solve the original problem?
Fact 1: let $$$k = 5$$$ and we have array $$$a=[1, 2, 4]$$$, and we want to count only good arrays where distinct elements are the same like in $$$a$$$. these arrays are $$$[1, 1, 1, 2, 4]$$$, $$$[1, 1, 2, 2, 4]$$$, $$$a[1, 1, 2, 4, 4]$$$, and so on... what we can see? this is a well-known distribution problem. so, the number of the good arrays we can use in the original problem is the number of ways to distribute $$$k - size(a)$$$ elements between $$$size(a)$$$ 'containers'. this is $$$C_{k-1, size(a)-1}$$$.
Fact 2: we can also see that in order to count the number of good arrays produced from the array $$$a$$$ in 'fact 1', the elements in the array $$$a$$$ don't matter to us. we need only $$$size(a)$$$. so, let see at all ours $$$dp_{i, j}$$$ — this number is equal to a number of arrays that can be used as $$$a$$$ in 'fact 1'. so, as elements in $$$a$$$ don't matter, let take the answer for an abstract array with length $$$i$$$ = $$$C_{k-1, i-1}$$$ and multiply this number with the number of arrays that can be length $$$i$$$ = $$$dp_{i, j}$$$ (note that we iterate also through all possible $$$j$$$-s).
the overall answer is the sum of all products computed in 'fact 2'
Given an array $$$a$$$ with distinct element, Suppose we increase the quantity of the $$$ith$$$ element by $$$x_{i}$$$. We want $$$(x_{1} + 1) + ... + (x_{size(a)} + 1) = k$$$. That is the same as $$$x_{1} + ... + x_{size(a)} = k - size(a)$$$ where all $$$x_{i}$$$ are non-negative integers. Therefore, the number of possible arrays that you can generate from $$$a$$$ is equal to the number of solutions of this equation, which is $$$C_{k - 1, size(a) - 1}$$$. Shouldn't be this formula instead of $$$C_{k - size(a) - 1, size(a) - 1}$$$ ?
you are right, sorry, i will upd now
My idea- Lets think of how many unique numbers the array can contain. It is not more than 17. Since even if we start with 1 and multiply 2 again and again then also $$$2^{17}$$$ exceeds $$$10^5$$$. So we conclude the array will contain contagious segments of almost $$$17$$$ unique numbers and ovbviously increasing. Now lets formulate the $$$dp$$$.
$$$dp[i][j]$$$ represent the number of different sequences with $$$j$$$ unique numbers such that the last digit is $$$i$$$. $$$dp[i][j]$$$ can be calculated as $$$dp[i][j] = summation(dp[x][j-1])$$$ where $$$x$$$ are divisor of $$$i$$$. Now calculate $$$dp2[i]$$$ denote the number of sequences of length $$$i$$$. This can be easily calculated from $$$summation(dp[x][i])$$$ where $$$x$$$ varies from $$$1$$$ to $$$n$$$. Now the task which remains is number of ways k can be divided into i segments which is stars and bars problem. Hence final answer is $$$summation(dp2[i]*nCr(k-1,i-1))$$$.
Can you fix the input?