let's suppose the case:
k = 1, n = 1000;
arr[] = {1,3,5,7,9,11,..........1999]
For this case, the answer can be 2^N, and according to the question we have to return an integer. Is it possible?
Please help someone.
Thank you.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
let's suppose the case:
k = 1, n = 1000;
arr[] = {1,3,5,7,9,11,..........1999]
For this case, the answer can be 2^N, and according to the question we have to return an integer. Is it possible?
Please help someone.
Thank you.
Name |
---|
Group all the numbers which give same remainder with $$$k$$$
Can we take any 2 elements which belong to different groups?
Now we need to find ways to take elements of one group together in our subset. Think in terms of combinatorics and DP. Since the answer can be quite big we should be calculating wrt some mod
hint4: Read the issues mentioned in the blog first, rather than rushing to growing contribution.
Better to help someone than making useless comments. My comment posted above would help anyone who doesn't get how to approach this problem. I don't think like you so XD
Since n<=10^3 we can solve the problem in O(n^2) by the naive implementation of biginteger.
Yes, it is possible. $$$2^{1000}$$$, which is the largest possible answer, has roughly $$$300$$$ digits. Multiplying numbers to get to a $$$300$$$ digits number shouldn't be too slow. If you still get TLE, you can just represent bigInt using base $$$10^{9}$$$, which would bring the number of digits down to a laughable $$$34$$$. If you are using Python then time limit shouldn't be a problem as well, as Python has built-in Karatsuba multiplication algorithm, which is fast.
Multiplying $$$k$$$ numbers (polynomials) in the case when answer has $$$n$$$ digits is $$$O(n^2)$$$. One may prove it with a reasoning simar to the one behind $$$O(n^2)$$$ knapsack on trees.