Sam and shopping

Hard
0/120
profile
Contributed by
3 upvotes
Asked in company
Directi

Problem statement

Sam goes to a shop having 'N' different items. The price of each of the items is 1 unit. He is a rich guy and has an infinite number of coins, each of value 'K' units. He wants to buy some things, but the total price of the items he buys must be multiple 'K'.

Find the number of ways in which he can buy some of the items from the shop.

You are required to print the answer modulo 100000.

Note: 
Buying no item is also a valid way
For Example: 
Input : N = 3, K = 2
Output : 4

Explanation:
There are 3 type of items; he can buy 2 items in 3 ways ({1,2}, {2,3} and {1,3}). and 0 items in 1 way, hence there will be a total of 4 ways.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains a single integer 'T' denoting the number of test cases to be run. Then the test cases follow.

The only line in the input contains two integers separated by a space, 'N' and 'K' denoting the number of items and the worth of one coin, respectively.
Output Format: 
For each test case, print an integer denoting the number of ways to buy some of the items for each test case, as specified above.
Note : 
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 50
1 <= N <= 10^12
1 <= K <= 10^3

Time Limit: 1 sec.
Sample Input 1:
2
3 1
2 2
Sample Output 1:
8
2
Explanation For Sample Output 1:
In the first test case, he can get by 1 item in 3 ways, 2 items in 3 ways, and 3 items 1 one way; hence total will be 7 and there will be one extra 0 item condition which makes answer = 8.

In the second test case he can buy 2 items in 1 way and 0 items in 1 way; hence answer = 2.
Sample Input 2:
2
8 3
5 3
Sample Output 2:
85
11
Hint

Try to compute the polynomial. 

Approaches (1)
FFT

In general, we have to compute the sum ∑ NC(M*K) modulo 100000 where M is from 0 to (N/K). 

Here, the binomial coefficients can be taken from the polynomial coefficients as (1+x)^n. 

We want to find the sum of the coefficients of x^i, where i is a multiple of K. We can take the powers modulo K here.

So, we can compute the coefficients of (1+x)^n using repeated squaring but only keep the first K coefficients. This will require O(log(n)) polynomial coefficients with, at most degree, K. We will use the efficient polynomial multiplication method FFT. 

Algorithm

  1. Make function multiply: it will multiply two polynomials and return the result.
  2. Make function do_truncation it will use to truncate the polynomial into the optimal.
  3. Make function result to get the result for given n, k, and mod.
  4. Inside the result function, we will call the multiply function for a given input.
  5. Make two variables x and y.
  6. Call result for parameters n, k, and mod =2^5 and store it in x
  7. Call result for parameters n, k, and mod =5^5 and store it in y.
  8. Make variable ans = x*3125*29 +y*32*293
  9. Return the ans.
Time Complexity

O(K*logN) Where K and N are input variables. 

Because we are iterating over K from 1 and using LogN complexity for each polynomial multiplication. 

Space Complexity

O(K), where K is the given input.

 

The space complexity due to the auxiliary arrays and to store the polynomial will be O(K).

Code Solution
(100% EXP penalty)
Sam and shopping
Full screen
Console