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 | 3757 |

2 | jiangly | 3590 |

3 | ksun48 | 3582 |

4 | Um_nik | 3539 |

5 | maroonrk | 3533 |

6 | slime | 3498 |

7 | djq_cpp | 3486 |

8 | Radewoosh | 3442 |

9 | cnnfls_csy | 3427 |

10 | ko_osaga | 3355 |

# | User | Contrib. |
---|---|---|

1 | -is-this-fft- | 184 |

2 | awoo | 180 |

3 | dario2994 | 171 |

4 | SecondThread | 168 |

4 | maroonrk | 168 |

4 | Um_nik | 168 |

7 | adamant | 166 |

8 | YouKn0wWho | 165 |

9 | errorgorn | 164 |

10 | antontrygubO_o | 162 |

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.

↑

↓

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/07/2022 08:46:14 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

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 numberiif the minimal summand isj,g(i,j) — number of partitions of numberiif the amount of summands isj. Thenf(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). Letpbe such number that (p- 1) * (p- 1) ≤n,p*p>n. Lets=p- 1. We compute values ofg(i,j) for alli= 1...n,j= 1...s. Then lets calculate values off(i,p) for alli= 1...n. Iterate through the number of summand here and express it through the fungtiong: . Then we can calculate values off(i,j) for alli= 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

ifaddition and subtraction areO(1) (e.g., modulo an integer).Edit:this is essentially the same as bciobanu's comment above.