You are given a number $$$n$$$, And we have two functions, We declare $$$P(S)$$$ for a set of numbers, product of all the numbers in the set, Also we declare $$$F(S)$$$ for a set of numbers, sum of all the numbers in the set, You have the set {$$$1, 2, 3, ... , n$$$} you have to calculate
for all non empty subsequences of {$$$1, 2, 3, ... , n$$$}, in the other words you have to provide a solution that calculates sum of $$$F(S)/P(S)$$$ for all non empty subsequences.
For example the answer for $$$n = 2$$$ is this :
for {$$$1$$$} sum is $$$1$$$ and product of numbers in it is $$$1$$$ so $$$F($$${$$$1$$$}$$$)/P($$${$$$1$$$}$$$)$$$ is $$$1/1 = 1$$$
for {$$$2$$$} sum is $$$2$$$ and product of numbers in it is $$$2$$$ so $$$F($$${$$$2$$$}$$$)/P($$${$$$2$$$}$$$)$$$ is $$$2/2 = 1$$$
- and for the last non empty subsequence {$$$1, 2$$$} sum is $$$3$$$ and product of the numbers in it is $$$2$$$ so $$$F($$${$$$1, 2$$$}$$$)/P($$${$$$1, 2$$$}$$$)$$$ is $$$3/2 = 1.5$$$
So the answer for $$$n = 2$$$ is $$$1 + 1 + 1.5 = 3.5$$$
Constraints :
$$$1 \le n \le 10^6$$$
Hope you enjoy the problem, I'll share my approach's proof after $$$24$$$ hours!
The sum is equivalent to taking the sum of $$$\frac{x}{P(S_i)}$$$ over all $$$x$$$ and over all $$$S_i$$$ that contain $$$x$$$.
For each $$$x$$$, the term is equivalent to summing the reciprocals of $$$P(X)$$$ over all $$$X$$$ that don't contain $$$x$$$, as the $$$x$$$-s will cancel out. This includes the empty set.
It can be easily shown by induction that $$$\sum_{X \subseteq S} \frac{1}{P(X)} = \frac{\prod_{x \in S}{(x+1)}}{P(S)}$$$. So each term of the sum can be computed using this formula and prefix/suffix products.
Complexity: $$$O(n)$$$ assuming $$$O(1)$$$ arithmetic.
Its pretty simple! I'll try to explain as simple as possible. First, for a set $$$S_i$$$ imagine splitting $$$F(S_i)/P(S_i)$$$. For example, if my set is $$$S = \{ 1,2,3 \}$$$. Then my splitting for $$$F(S)/P(S)$$$ will be: $$$1*(\frac{1}{1*2*3}) + 2*(\frac{1}{1*2*3}) + 3*(\frac{1}{1*2*3})$$$. Every such split has some coefficient of every number from $$$1$$$ to $$$n$$$. In this example coefficients are ($$$\frac{1}{6} , \frac{1}{6},\frac{1}{6},0,0..)$$$.
What would be the coefficient of some number $$$i$$$ in my entire sum? It will be the in form $$$\sum(\frac{1}{P_j})$$$, where $$$P_j$$$ means the product of a subset having $$$i$$$. I sum this over all subsets containing $$$i$$$. So, imagine selecting some numbers from a bunch of $$$(\frac{1}{1},\frac{1}{2},\frac{1}{3},...\frac{1}{n})$$$ under the condition that $$$\frac{1}{i}$$$ must be selected, then adding them up. It is easy to see it will be $$$(1+\frac{1}{1})(1+\frac{1}{2})(1+\frac{1}{3})..(\frac{1}{i})..(1+\frac{1}{n})$$$. This is because while multiplying, every number $$$t$$$ (except $$$i$$$) has a choice of getting selected or rejected (hence, $$$1$$$ or $$$\frac{1}{t}$$$). However, we gotta select $$$\frac{1}{i}$$$, so I multiply my $$$\frac{1}{i}$$$.
So, now we got the coefficient of number $$$i$$$. Final answer will be:
Summing this up, everything will magically cancel out! (The Aha! moment) and you'll get the result :)
After reading this type of blogs I always think that I am very bad at mathematics.
How to be good. Anyone who can help?
nice problem