Interesting hard problem! [Challenge]
source link: http://codeforces.com/blog/entry/105077
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Interesting hard problem! [Challenge]
By hunter_of_alts, 17 hours ago,
You are given a number nn, And we have two functions, We declare P(S)P(S) for a set of numbers, product of all the numbers in the set, Also we declare F(S)F(S) for a set of numbers, sum of all the numbers in the set, You have the set {1,2,3,...,n1,2,3,...,n} you have to calculate
∑2n−1i=1(F(Si)/P(Si))∑i=12n−1(F(Si)/P(Si))for all non empty subsequences of {1,2,3,...,n1,2,3,...,n}, in the other words you have to provide a solution that calculates sum of F(S)/P(S)F(S)/P(S) for all non empty subsequences.
For example the answer for n=2n=2 is this :
for {11} sum is 11 and product of numbers in it is 11 so F(F({11})/P()/P({11})) is 1/1=11/1=1
for {22} sum is 22 and product of numbers in it is 22 so F(F({22})/P()/P({22})) is 2/2=12/2=1
- and for the last non empty subsequence {1,21,2} sum is 33 and product of the numbers in it is 22 so F(F({1,21,2})/P()/P({1,21,2})) is 3/2=1.53/2=1.5
So the answer for n=2n=2 is 1+1+1.5=3.51+1+1.5=3.5
Constraints :
1≤n≤1061≤n≤106
Hope you enjoy the problem, I'll share my approach's proof after 2424 hours!
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK