Функція F (Розбір)

Функція F#12303

Автор проблеми:	De3b0o
Підготовлено:	De3b0o
Редагував:	Hasan Saleh (MathModel)

Розв'язок

Для рядка $s$ та цілого числа $x \geq 1$ x \ge 1, якщо рядок $s$ вже має $x$ або більше однакових сусідніх символів, то відповідь буде або $0$ , або $1$ . $0$ , якщо перші $x$ однакових сусідніх символів - це нулі, і $1$ в іншому випадку.

В іншому випадку, якщо $s$ не має $x$ або більше однакових сусідніх символів. Нас цікавить лише максимальний однаковий суфікс.

Припустимо, що довжина суфікса дорівнює $y$ і припустимо, що символи - це одиниці, а не нулі (якщо це були б нулі, відповідь дорівнює $1 -$ відповідь, якщо це були б одиниці). Відповідь дорівнює $\frac{1}{2 ^{x - y}} + (\frac{2 ^{x - y} - 1}{2 ^{x - y}}) (\frac{2 ^{x - 1} - 1}{2 ^{x} - 1})$ \frac{1}{2^{x-y}} + (\frac{2^{x-y}-1}{2^{x-y}})(\frac{2^{x-1}-1}{2^x-1}).

Доказ: У нас є дві можливості:

Перша полягає в тому, що перші $x - y$ x-y випадкових символів дорівнюють $1$ , ймовірність цього становить $\frac{1}{2 ^{x - y}}$ \frac{1}{2^{x-y}}, а ймовірність того, що останній символ буде $1$ , дорівнює $1$ (тому що тоді ми отримаємо $y + x - y = x$ y+x-y=x сусідніх одиниць, і процес закінчиться відразу).

Друга полягає в тому, що принаймні один з перших $x - y$ x-y символів не дорівнює $1$ (не важливо, які саме), ймовірність цього становить $\frac{2 ^{x - y} - 1}{2 ^{x - y}}$ \frac{2^{x-y}-1}{2^{x-y}} ( $1 -$ ймовірність того, що всі вони дорівнюють $1$ ), а ймовірність того, що останній символ буде $1$ , дорівнює $\frac{2 ^{x - 1} - 1}{2 ^{x} - 1}$ \frac{2^{x-1}-1}{2^x-1}.

Отже, відповідь повинна бути:

(Ймовірність першого випадку)(Ймовірність отримати $1$ , якщо це сталося) + (Ймовірність другого випадку)(Ймовірність отримати $1$ , якщо це сталося)

Що дорівнює наведеній вище формулі.

Тепер пояснимо, чому ймовірність отримати $1$ дорівнює $\frac{2 ^{x - 1} - 1}{2 ^{x} - 1}$ \frac{2^{x-1}-1}{2^x-1} у другому випадку.

Це те ж саме, що ймовірність отримати $1$ , починаючи з $s = 0$ s = 0 (тому що після додавання першого $0$ новий максимальний однаковий суфікс - це останній символ, який є $0$ ).

Позначимо $p$ ймовірність отримати $0$ , починаючи з $s = 0$ s=0.

Тоді:

$p = z + (1 - z) (1 - p)$ p = z + (1-z)(1-p), де $z = \frac{1}{2 ^{x - 1}}$ z = \frac{1}{2^{x-1}}

$p = z + (1 - z) (1 - p) = z + 1 - z - p + z \cdot p$ p = z + (1-z)(1-p) = z + 1 - z - p +z \cdot p

$(2 - z) \cdot p = 1$ (2-z)\cdot p = 1

$p = \frac{1}{2 - z} = \frac{1}{2 - \frac{1}{2 ^{x - 1}}}$ p = \frac{1}{2-z} = \frac{1}{2-\frac{1}{2^{x-1}}}

Ми можемо помножити чисельник і знаменник на $2^{x - 1}$ 2^{x-1}

$p = \frac{2 ^{x - 1}}{2 ^{x} - 1}$ p = \frac{2^{x-1}}{2^x - 1}

А ймовірність отримати $1$ , починаючи з $s = 0$ s=0, замість того, щоб отримати $0$ , дорівнює $1 - p = \frac{2 ^{x} - 1 - 2 ^{x - 1}}{2 ^{x} - 1} = \frac{2 ^{x - 1} - 1}{2 ^{x} - 1}$ 1-p = \frac{2^x - 1 - 2^{x-1}}{2^x - 1} = \frac{2^{x-1} - 1}{2^x - 1}.

Складність $O (q \cdot lo g (max (x)))$ \mathcal{O}(q \cdot \log(\max(x))).


#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define in insert
#define pb push_back
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define cans cout << ans << "\n";
#define yes cout << "YES" << "\n";
#define no cout << "NO" << "\n";
#define pll pair<ll, ll>
#define lin cout << "\n";
#define mid ((l + r) / 2)
#define lc (2 * x)
#define rc (2 * x + 1)
#define double long double

using namespace std;

const ll N = 5e5+9 , m = 1e9+7;

ll fp(ll x , ll y)
{
    if(y==0)
        return 1;
    ll z = fp(x,y/2);
    if(y%2)
        return z*z%m*x%m;
    else
        return z*z%m;
}

ll q,ans,pro,z,x,p,d,zz;
char c,pr;
char e[N];

ll mod(ll x)
{
    x%=m;
    x+=m;
    x%=m;
    return x;
}

int main()
{
    d3
    ll T = 1;
    cin >> T;
    while(T--)
    {
        cin >> q;
        pr='0';
        p=0;
        for(int i = 1 ; q+10>=i ; i++)
            e[i]='2';
        for(int qq = 1 ; q>=qq ; qq++)
        {
            cin >> c >> x;
            if(c==pr)
                p++;
            else
                pr=c,p=1;
            if(e[p]=='2')
                e[p]=c;
            if(x<=q+10&&e[x]!='2')
            {
                if(e[x]=='1')
                    cout << 1 << '\n';
                else
                    cout << 0 << '\n';
                continue;
            }
            pro = mod(fp(2,x-1)-1);
            d = mod(fp(2,x)-1);
            pro=mod(pro*fp(d,m-2));
            z=fp(fp(2,x-p),m-2);
            zz = mod(1 - z);
            ans = mod(z + zz*pro);
            if(c=='0')
                ans=mod(1-ans);
            cout << ans << '\n';
        }
    }
}