SPOJ.com - Problem PARCARD2

PARCARD2 - Partition function (HARD)

no tags

You need to output the number of distinct ways of representing n as a sum of natural numbers (with order irrelevant) for given integer n.

n, 0 ≤ n ≤ 10⁸

Input:
2013

Output:
6805659785780163657391920602286596663406217911



	[Rampage] Blue.Mary: 2023-12-09 00:17:35 Actually no need to read the paper mentioned in other comments. Python library Sympy has already implemented the solution to this problem, all you need is to find it out. Last edit: 2023-12-09 00:19:02
	Ishan: 2022-06-16 09:19:39 how many n per test file are there(I guess one. still confirming) and how many test files are there? And are the test data log uniformly distributed ? Last edit: 2022-06-16 09:29:51
	softxide: 2017-08-03 08:10:17 Getting TLE but logic working good for 2013 . I used DP and then for incrementing total count I am using technique for adding large numbers as we do in school .Any other approach if someone can share ? --ans--> Google "Efficient implementation of the Hardy–Ramanujan–Rademacher formula" Last edit: 2018-07-14 01:28:29
	BA_AK: 2013-12-08 11:55:04 A very difficult sum! 10^8 is too much!
	Yashpal: 2013-07-04 09:13:43 10^8 is very large value to be computing... i hav completed the easy part in .58 s... but not able to extend upto 10^8.. can u give me some link about integer partition so that i can learn more about it....:) --ans--> The task is very hard. Google "Hardy-Ramanujan-Rademacher formula" RE-->Hey i implement the hardy's formula but its it giving wrong answer....here is my code.. <snip> how can i accurate the ans?? Last edit: 2022-09-10 13:27:24