Product of sum of all subarrays of an array

[oyehoye696906]

I've been able to find sum of all subarrays, product of all subarrays, product of the sum of all subarrays in O(n) but I'm not able to find a pattern for this.

Explanation:
array = {1,2,3}
ans = (1)*(2)*(3)*(1+2)*(2+3)*(1+2+3) = 540

There can be 10e5 elements in the array.
Can someone please help me find a way to solve this in linear time?
Thank you!

[dutch]

What are the limits of the values?
Can they be over 32-bits?
Can they be negative?

[oyehoye696906]

All values are less than 32 bits and greater than equal to zero.

[dutch]

Why do you only have (1+2) and (2+3).
What about (1+3) ?

At any rate, the value as you've described it could be millions of decimal digits long.
Does that sound reasonable to you?

If you have a link to the problem, post it.

[oyehoye696906]

1+3 can't be included as its not a subarray, we're talking about contiguous subarrays like [1], [2], [3], [1,2], [2,3], [1,2,3].

Yeah, I know the final value can be infinitely large, we can later apply modulus to improve that.

Actually I myself was working on such stuff so there doesn't exist a specific problem.

[dutch]

Actually I myself was working on such stuff so there doesn't exist a specific problem.

okay

You say you already know "product of the sum of all subarrays".
Isn't that exactly what you're doing?

[oyehoye696906]

I don't why you're so confused with the question. Simply the question goes as follows that we need to calculate product of sum of all subarrays (example given in previous replies and the post itself.) I've already wasted around a week trying to figure out a way to get this in linear time but I didn't succeed. That's why I'm asking someone to help me I'm getting nowhere in this question.
Constraints:
array size: 1 < size < 10e5
elements: 0 <= element <= 10e9
Time complexity: <= O(nlogn)

[lastchance]

oyehoye696906 wrote:

I don't why you're so confused with the question.

Your elements can be of size 10⁹. There could be up to 10⁵ of them. And you seriously think you are going to represent their product in an integer variable?

Or are you going to give your answer modulo something?

State the whole problem. State which particular competition it comes from.

[againtry]

This appears to be some sort of a starting point to find out the real nature of this problem.

https://www.geeksforgeeks.org/sum-of-all-subarrays/
https://algorithms.tutorialhorizon.com/sum-of-all-sub-arrays-in-on-time/

[oyehoye696906]

@lastchance, We'll obviously use modulo like 10e9+7 to get the final answer. I myself thought of this problem and I was searching for the answer.

[dutch]

I don't why you're so confused with the question.

You are obviously the one who is totally confused here.
I know exactly what you are looking for.
You are looking for the "product of the sum of all subarrays".
That's what you are looking for, whether you know it or not.
(I can't fathom why you don't know that! Jesus!)
Anyway, you also state in your original braindead question that you already know the "product of the sum of all subarrays".
Now can your tiny brain understand the problem?

[dhayden]

There are N(N+1)/2 subarrays so you have that many factors. Clearly multiplying them is O(N²) so to do this faster, you need some way to reduce the factors. I've been playing around with this a little and I can't figure anything out.

What makes you think this can be done in O(N) time?