Not Very Powerful#12464

Not Very Powerful (Editorial)

Problem Author:	Hadi Takla (TaklaOI)
Prepared by:	Hadi Takla (TaklaOI)
Edited by:	Hadi Takla (TaklaOI)

Solution

Fact : An index $i$ in the original array can have any index $j$ ( $1 \leq j \leq i$ 1\le j \le i) in the subsequence.

if we want the index $i$ to have the index $j$ in the subsequence , we should choose $j - 1$ j-1 element from the $i - 1$ i-1 elements before $i$ , and we can choose as we want from the next $n - i$ n-i elements.

so the number of the subsequences that have the index $i$ in the original array as $j$ in the subsequence is.

(j - 1 i - 1) \cdot 2^{n - i}

\binom{i-1}{j-1} \cdot 2^{n - i}

so we can calculate the answer using the formula.

an s = i = 1 \sum n j = 1 \sum i (j - 1 i - 1) \cdot 2^{n - i} \cdot (- a_{i})^{j}

ans = \sum_{i=1}^{n} \sum_{j=1}^{i} \binom{i-1}{j-1} \cdot 2^{n-i} \cdot (-a_i)^j

= i = 1 \sum n (2^{n - i} \cdot j = 1 \sum i (j - 1 i - 1) \cdot (- a_{i})^{j})

= \sum_{i=1}^{n} (2^{n-i} \cdot \sum_{j=1}^{i} \binom{i-1}{j-1}\cdot (-a_i)^j)

but that's an $O (n^{2})$ \mathcal{O}(n^2) solution which cannot pass the constraints.

so let $co n_{i} = \sum_{j = 1}^{i} (j - 1 i - 1) \cdot (- a_{i})^{j}$ con_i = \sum_{j=1}^{i} \binom{i-1}{j-1} \cdot (-a_i)^j.

the answer will be

an s = i = 1 \sum n 2^{n - i} \cdot co n_{i}

ans = \sum_{i=1}^{n} 2^{n - i} \cdot con_i

Now , let's write $co n_{i}$ con_i as follows.

co n_{i} = j = 1 \sum i (j - 1 i - 1) \cdot (- 1)^{j} \cdot a_{i}^{j}

con_i = \sum_{j=1}^{i} \binom{i-1}{j-1} \cdot (-1)^j \cdot a_i ^ j

So we can split even indices alone and odd one alone.

so we can write $co n_{i} = e v e n_{i} - o d d_{i}$ con_i = even_i - odd_i

where $e v e n_{i}$ even_i is the sum on even $j$ values , and $o d d_{i}$ odd_i is the sum on odd $j$ values.

now let's try to simplify $e v e n_{i}$ even_i and $o d d_{i}$ odd_i.

when $j$ is even , j-1 is odd.

so if we let $2 k + 1 = j - 1$ 2k + 1 = j-1 $\Rightarrow$ $j = 2 k + 2$ j = 2k + 2.

we can write $e v e n_{i}$ even_i as follows:

k = 0 \sum ⌊ \frac{i - 1}{2} ⌋ (2 k + 1 i - 1) \cdot a_{i}^{2 k + 2}

\sum_{k=0}^{\lfloor \frac{i-1}{2} \rfloor} \binom{i-1}{2k+1} \cdot a_i ^ {2k+2}

which is equal to

a_{i} \cdot k = 0 \sum ⌊ \frac{i - 1}{2} ⌋ (2 k + 1 i - 1) \cdot a_{i}^{2 k + 1}

a_i \cdot \sum_{k=0}^{\lfloor \frac{i-1}{2} \rfloor} \binom{i-1}{2k+1} \cdot a_i ^ {2k+1}

now we can see that $\sum_{k = 0}^{⌊ \frac{i - 1}{2} ⌋} (2 k + 1 i - 1) \cdot a_{i}^{2 k + 1}$ \sum_{k=0}^{\lfloor \frac{i-1}{2} \rfloor} \binom{i-1}{2k+1} \cdot a_i ^ {2k+1} is the sum of even places in a bionominal expansion which is equal to

\frac{( 1 + a _{i} ) ^{i - 1} - ( 1 - a _{i} ) ^{i - 1}}{2}

\frac {(1 + a_i)^{i-1} - (1 - a_i)^{i-1}}{2}

so $e v e n_{i}$ even_i will be equal to $a_{i} \cdot \frac{( 1 + a _{i} ) ^{i - 1} - ( 1 - a _{i} ) ^{i - 1}}{2}$ a_i \cdot \frac {(1 + a_i)^{i-1} - (1 - a_i)^{i-1}}{2}.

now the same way for $o d d_{i}$ odd_i.

when $j$ is odd, j-1 is even.

so if we let $2 k = j - 1$ 2k = j-1 $\Rightarrow$ $j = 2 k + 1$ j = 2k + 1.

we can write $o d d_{i}$ odd_i as follows:

k = 0 \sum ⌊ \frac{i - 1}{2} ⌋ (2 k i - 1) \cdot a_{i}^{2 k + 1}

\sum_{k=0}^{\lfloor \frac{i-1}{2} \rfloor} \binom{i-1}{2k} \cdot a_i ^ {2k+1}

which is equal to

a_{i} \cdot k = 0 \sum ⌊ \frac{i - 1}{2} ⌋ (2 k i - 1) \cdot a_{i}^{2 k}

a_i \cdot \sum_{k=0}^{\lfloor \frac{i-1}{2} \rfloor} \binom{i-1}{2k} \cdot a_i ^ {2k}

we can see that $\sum_{k = 0}^{⌊ \frac{i - 1}{2} ⌋} (2 k i - 1) \cdot a_{i}^{2 k}$ \sum_{k=0}^{\lfloor \frac{i-1}{2} \rfloor} \binom{i-1}{2k} \cdot a_i ^ {2k} is the sum of odd places in a bionominal expansion which is equal to.

\frac{( 1 + a _{i} ) ^{i - 1} + ( 1 - a _{i} ) ^{i - 1}}{2}

\frac {(1 + a_i)^{i-1} + (1 - a_i)^{i-1}}{2}

so $o d d_{i}$ odd_i will be equal to $a_{i} \cdot \frac{( 1 + a _{i} ) ^{i - 1} + ( 1 - a _{i} ) ^{i - 1}}{2}$ a_i \cdot \frac {(1 + a_i)^{i-1} + (1 - a_i)^{i-1}}{2}.

returning to $co n_{i}$ con_i = $e v e n_{i} - o d d_{i}$ even_i - odd_i.

so $co n_{i}$ con_i = $a_{i} \cdot \frac{( 1 + a _{i} ) ^{i - 1} - ( 1 - a _{i} ) ^{i - 1}}{2} - a_{i} \cdot \frac{( 1 + a _{i} ) ^{i - 1} + ( 1 - a _{i} ) ^{i - 1}}{2}$ a_i \cdot \frac {(1 + a_i)^{i-1} - (1 - a_i)^{i-1}}{2} - a_i \cdot \frac {(1 + a_i)^{i-1} + (1 - a_i)^{i-1}}{2}.

= $- a_{i} \cdot (1 - a_{i})^{i - 1}$ -a_i \cdot (1-a_i)^{i-1}.

$an s = \sum_{i = 1}^{n} 2^{n - 1} \cdot co n_{i}$ ans = \sum_{i=1}^{n} 2^{n-1} \cdot con_i.

an s = i = 1 \sum n - 2^{n - i} \cdot a_{i} \cdot (1 - a_{i})^{i - 1}

ans = \sum_{i=1}^{n} -2^{n-i} \cdot a_i \cdot (1 - a_i) ^ {i-1}

Time complexity : $O (n log (max (a_{i}))) .$ \mathcal{O}(n \text{log}(\text{max}(a_i))).

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define F first
#define S second
using namespace std;
const int N = 2e5 + 1;
const int M = 1e9 + 7;
int add(int a,int b)
{
    a %= M;
    b %= M;
    return (a+b+M)%M;
}
int sub(int a,int b)
{
    a %= M;
    b %= M;
    return (a-b+M)%M;
}
int mul(int a,int b)
{
    a %= M;
    b %= M;
    int res = a*b;
    res %= M;
    res += M;
    res %= M;
    return res;
}
int pwr(int x,int y)
{
    if(y == 0)
    return 1;
    int res = pwr(x,y/2);
    res = mul(res,res);
    if(y % 2)
    res = mul(res , x);
    return res;
}
int divi(int a,int b)
{
    return mul(a , pwr(b,M-2));
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int tc = 1;
    cin>>tc;
    while(tc--)
    {
        int n;
        cin>>n;
        int ans = 0;
        int a[n+1];
        for(int i=1;i<=n;i++){
            cin>>a[i];
            int tmp = pwr(2 , n-i);
            tmp = mul(tmp , a[i]);
            tmp = mul(tmp , pwr(sub(1 , a[i]) , i-1));
            tmp = mul(tmp , -1);
            ans = add(ans , tmp);
        }
        cout<<ans<<endl;
    }
}