F Funksiyası#12303

F Funksiyası (Həll təhlili)

Problem Müəllifi:	De3b0o
Hazırlayan:	De3b0o
Redaktə edən:	Hasan Saleh (MathModel)

Həll

Bir $s$ simvolu və bir tam ədəd $x \geq 1$ x \ge 1 üçün, əgər $s$ simvolunda artıq $x$ və ya daha çox bərabər ardıcıl simvollar varsa, cavab ya $0$ ya da $1$ -dir. $0$ əgər ilk $x$ bərabər ardıcıl simvollar sıfırlardır, $1$ isə əks halda.

Əks halda, əgər $s$ -də $x$ və ya daha çox bərabər ardıcıl simvollar yoxdursa, yalnız maksimum bərabər sonluqla maraqlanırıq.

Gəlin sonluğun uzunluğunu $y$ adlandıraq və simvolların birlər olduğunu və sıfır olmadığını fərz edək (əgər sıfır olsaydılar, cavab $1 -$ birlər olsaydı olan cavab olardı). Cavab $\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})-dir.

Sübut: İki ehtimalımız var:

Birincisi, ilk $x - y$ x-y təsadüfi simvollar $1$ -ə bərabərdir, bunun baş vermə ehtimalı $\frac{1}{2 ^{x - y}}$ \frac{1}{2^{x-y}}-dir və son simvolun $1$ olması ehtimalı $1$ -dir (çünki o zaman $y + x - y = x$ y+x-y=x ardıcıl birlərimiz olacaq və proses dərhal başa çatacaq).

İkincisi, ilk $x - y$ x-y simvolların ən azı biri $1$ -ə bərabər deyil (hansıların olduğu əhəmiyyətli deyil), bunun baş vermə ehtimalı $\frac{2 ^{x - y} - 1}{2 ^{x - y}}$ \frac{2^{x-y}-1}{2^{x-y}}-dir ( $1 -$ onların hamısının $1$ olması ehtimalı) və son simvolun $1$ olması ehtimalı $\frac{2 ^{x - 1} - 1}{2 ^{x} - 1}$ \frac{2^{x-1}-1}{2^x-1}-dir.

Beləliklə, cavab aşağıdakı kimi olmalıdır:

(Birinci halın ehtimalı)(Baş verərsə $1$ -ə çatma ehtimalı) + (İkinci halın ehtimalı)(Baş verərsə $1$ -ə çatma ehtimalı)

Bu, yuxarıdakı formulaya bərabərdir.

İndi ikinci halda $1$ -ə çatma ehtimalının $\frac{2 ^{x - 1} - 1}{2 ^{x} - 1}$ \frac{2^{x-1}-1}{2^x-1}-ə bərabər olduğunu izah edəcəyik.

Bu, $s = 0$ s = 0 ilə başlamaqla $1$ -ə çatma ehtimalı ilə eynidir (çünki ilk $0$ əlavə etdikdən sonra yeni maksimum bərabər sonluq son simvol olan $0$ -dır).

Gəlin $p$ -ni $s = 0$ s=0 ilə başlamaqla $0$ -ə çatma ehtimalı adlandıraq.

Sonra:

$p = z + (1 - z) (1 - p)$ p = z + (1-z)(1-p), burada $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}}}

Müqayisə edərək, pay və məxrəci $2^{x - 1}$ 2^{x-1} ilə vurmaq olar.

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

Və $s = 0$ s=0 ilə başlamaqla $1$ -ə çatma ehtimalı $0$ -ə çatma ehtimalı əvəzinə $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}-dir.

Komplekslik $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 << "BƏLİ" << "\n";
#define no cout << "XAHŞI" << "\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';
        }
    }
}