Hi Everyone.
Now I'm wondering how to find the number of partition of an integer N(<=10^5).
Any advice?
The number of partition of 4 is 5.
4 = 4.
4 = 3 + 1.
4 = 2 + 2.
4 = 2 + 1 + 1.
4 = 1 + 1 + 1 + 1.
Thank You.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3821 |
3 | Benq | 3736 |
4 | Radewoosh | 3631 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3388 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Hi Everyone.
Now I'm wondering how to find the number of partition of an integer N(<=10^5).
Any advice?
The number of partition of 4 is 5.
4 = 4.
4 = 3 + 1.
4 = 2 + 2.
4 = 2 + 1 + 1.
4 = 1 + 1 + 1 + 1.
Thank You.
Name |
---|
Auto comment: topic has been updated by YogayoG (previous revision, new revision, compare).
I came up with following solution. It uses the fact that either minimal summand in the partition or ammount of summands is not too big. Let arrange the summands in the partition in the non decreasing order. Denote f(i, j) — number of partitions of number i if the minimal summand is j, g(i, j) — number of partitions of number i if the amount of summands is j. Then f(i, j) = f(i - j, j) + f(i, j + 1) (we either put j as a new summand or increase the minimal summand), g(i, j) = g(i - 1, j - 1) + g(i - j, j) (we either put 1 as a new summand or we will have all the summands are greater than 1 then decrease all of them by 1 and return to the state when all the summands are greater or equal than 1). Let p be such number that (p - 1) * (p - 1) ≤ n, p * p > n. Let s = p - 1. We compute values of g(i, j) for all i = 1...n, j = 1...s. Then lets calculate values of f(i, p) for all i = 1...n. Iterate through the number of summand here and express it through the fungtion g: . Then we can calculate values of f(i, j) for all i = 1...n, j = 1...s. Time and space complexity are . It seems pretty amazing to me that there is such a solution while before I encountered with such a problem and didn't know that it's possible to solve it with such complexity. Is it known that we can solve this problem with such complexity or better?
You can also compute it using pentagonal numbers in . It's a bit easier to implemenent, but much less intuitive than your solution.
bciobanu I have read that before. And I can't understand why it works. Thanks for pointing me that it's easier to implement, I will trying to understand it.
Thank you ABalobanov for your solution. And seems your solution surely will pass the time limit.
On the OEIS page, the formula involving A001318 looks like it yields an solution if addition and subtraction are O(1) (e.g., modulo an integer).
Edit: this is essentially the same as bciobanu's comment above.