Не дуже потужний#12464

Не дуже потужний (Розбір)

Автор задачі:	Hadi Takla (TaklaOI)
Підготував:	Hadi Takla (TaklaOI)
Відредагував:	Hadi Takla (TaklaOI)

Розв'язок

Факт: індекс $i$ у вихідному масиві може мати будь-який індекс $j$ ( $1 \leq j \leq i$ 1\le j \le i) у підпослідовності.

Якщо ми хочемо, щоб індекс $i$ мав індекс $j$ у підпослідовності, ми повинні вибрати $j - 1$ j-1 елемент із $i - 1$ i-1 елементів перед $i$ , а з наступних $n - i$ n-i елементів можемо вибирати довільно.

Отже, кількість підпослідовностей, у яких індекс $i$ вихідного масиву є $j$ -м у підпослідовності, дорівнює:

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

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

Таким чином, ми можемо обчислити відповідь за формулою:

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)

Але це розв'язок за $O (n^{2})$ \mathcal{O}(n^2), який не вкладається в обмеження.

Тому нехай $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.

Відповідь матиме вигляд:

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

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

Тепер запишемо $co n_{i}$ con_i наступним чином:

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

Отже, ми можемо окремо виділити парні та непарні індекси.

Тому запишемо $co n_{i} = e v e n_{i} - o d d_{i}$ con_i = even_i - odd_i,

де $e v e n_{i}$ even_i — сума за парними значеннями $j$ , а $o d d_{i}$ odd_i — сума за непарними значеннями $j$ .

Тепер спробуємо спростити $e v e n_{i}$ even_i та $o d d_{i}$ odd_i.

Коли $j$ парне, $j - 1$ j-1 непарне.

Тому якщо покладемо $2 k + 1 = j - 1$ 2k + 1 = j-1 $\Rightarrow$ $j = 2 k + 2$ j = 2k + 2,

ми можемо записати $e v e n_{i}$ even_i наступним чином:

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}

що дорівнює

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}

Тепер бачимо, що $\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} — це сума елементів на парних позиціях у біноміальному розкладі, що дорівнює:

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

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

Отже, $e v e n_{i}$ even_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}.

Тепер аналогічно для $o d d_{i}$ odd_i.

Коли $j$ непарне, $j - 1$ j-1 парне.

Тому якщо покладемо $2 k = j - 1$ 2k = j-1 $\Rightarrow$ $j = 2 k + 1$ j = 2k + 1,

ми можемо записати $o d d_{i}$ odd_i наступним чином:

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}

що дорівнює

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}

Бачимо, що $\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} — це сума елементів на непарних позиціях у біноміальному розкладі, що дорівнює:

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

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

Отже, $o d d_{i}$ odd_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}.

Повертаючись до $co n_{i}$ con_i = $e v e n_{i} - o d d_{i}$ even_i - odd_i:

$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}

Часова складність: $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;
    }
}