N=4

Factor 1,2,4 sum of product of substring

ans=(1+2+4+1*2+1*4+2*4+1*2*4)%(10^9+7)=29

How to solve this in O(no. Of factors)

N=4

Factor 1,2,4 sum of product of substring

ans=(1+2+4+1*2+1*4+2*4+1*2*4)%(10^9+7)=29

How to solve this in O(no. Of factors)

Problem Link please

for each factor, add 1 to it and then multiply. so you get expression

(a+1). (b+1) . (c+1) . … (n+1) upto n factors

if u observe carefully, you’ll see it contains all combinations of a,b,c,… n since to get just ‘a’ , you can multiply it with all other 1s.

Also how we got this?

Its just a polynomial (x+a).(x+b). … (x+n) where a,b,…n are factors and putting x=1 we get all the sum of all coefficients of this polynomial.

all coefficients contacts all the possible combination there are or the power set of all factors.

2 Likes

1 Like

One more thing: Subtract the extra 1 produce due = (1 * 1 * 1 * 1…)

1 Like