N=4
Factor 1,2,4 sum of product of substring
ans=(1+2+4+12+14+24+12*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