Loading...

奇奇怪怪的考试题

check评论:0 条 remove_red_eye浏览量:172 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-12-05

你有$m$点血,有$n$秒,第$i$秒有$p_i$概率掉一点血,血量小于$0$算$0$,问每一秒血量期望

令$dp[i][j]$代表第$i$秒有$j$滴血概率,显然$dp[i][j]=dp[i-1][j+1]*p[i]+dp[i-1][j]*(1-p[i])$,答案就是$\sum\limits_{i=1}^m i*dp[n][i]$

展开这个式子,显然他等于$\sum\limits_{i=1}^m dp[n-1][i]*(i-p[n])$

令$Q[i]=\sum\limits_{j=1}^m dp[i][j]$

则$Q[n]=Q[n-1]-p[n]*\sum\limits_{i=1}^m dp[n-1][i]$

我们令$k[i]$代表第$i$轮操作结束后$1$恰好为$1$的概率,显然只有大于$0$的血量才有贡献,所以后面的式子可以转化为$1-\sum\limits_{i=1}^m p[i]k[i-1]$

现在的问题是求$k[i]$,考虑每个概率的$OGF$,就是若干个多项式相乘,即$\prod((1-p[i])+p[i]x)$,然后取指数为$m-1$项的系数即可

然后我不会分治$FFT$=w=,考虑把它分成很多块,快内维护小多项式暴力乘,再维护个前缀大多项式,每次小多项式大小到了块大小就乘进大多项式即可

复杂度$O(n\sqrt{nlogn})$,很奇怪,块大小$1100-4500$都能过

/*deco loves Chino*/
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
const int mod=998244353,g=3;
#define int long long
int a[400010],n,m,huge[400010],sma[400010],r[400010],lim,block;
int q[400010],k[400010],pre[4],t,calc[400010],len,l,Q[100010];
int ksm(int a,int qaq)
{
    int res=1;
    while(qaq)
    {
        if(qaq&1)
        {
            res=res*a%mod;
        }
        a=a*a%mod;
        qaq>>=1;
    }
    return res;
}
void NTT(int *x,int flag)
{
    for(int i=0;i<lim;i++)
    {
        if(i<r[i])
        {
            swap(x[i],x[r[i]]);
        }
    }
    for(int mid=1;mid<lim;mid<<=1)
    {
        int wn=ksm(g,flag==1?(mod-1)/(mid<<1):(mod-1-(mod-1)/(mid<<1)));
        for(int k=0,r=(mid<<1);k<lim;k+=r)
        {
            int w=1;
            for(int i=0;i<mid;i++,w=w*wn%mod)
            {
                int dx=x[i+k],dy=x[i+mid+k]*w%mod;
                x[i+k]=(dx+dy)%mod,x[i+mid+k]=(dx-dy+mod)%mod;
            }
        }
    }
}
int read()
{
    int x=0;
    char ch=getchar();
    while(!isdigit(ch)) 
    {
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=x*10+(ch-'0');
        ch=getchar();
    }
    return x;
}
signed main()
{
    //freopen("in.in","r",stdin);
    //freopen("d1.out","w",stdout);
    cin>>n>>m;
    Q[0]=m;
    block=2800;
    for(int i=1;i<=n;i++)
    {
        int a,b;
        a=read(),b=read();
        a%=mod,b=ksm(b,mod-2);
        q[i]=a*b%mod;
    }
    if(m==1)
    {
        k[0]=1;
    }
    for(int p=1;p<=n;p++)
    {
        if((p-1)%block==0)
        {
            t=1;
            sma[0]=(1-q[p]+mod)%mod;
            sma[1]=q[p];
        }
        else
        {
            for(int i=0;i<=t+1;i++)
            {
                calc[i]=0;
            }
            pre[0]=(1-q[p]+mod)%mod;
            pre[1]=q[p];
            for(int i=0;i<=t;i++)
            {
                for(int j=0;j<=1;j++)
                {
                    calc[i+j]+=sma[i]*pre[j];
                    calc[i+j]%=mod;
                }
            }
            for(int i=0;i<=t+1;i++)
            {
                sma[i]=calc[i];
            }
            ++t;
        }
        if(p<=block)
        {
            if(m<=1+t)
            {
                k[p]=sma[m-1];
            }
            if(p==block)
            {
                for(int i=0;i<=t;i++)
                {
                    huge[i]=sma[i];
                }
                len=t;
            }
        }
        else
        {
            for(int i=min(t,m-1);i>=0&&(m-1-i)<=len;i--)
            {
                k[p]=(k[p]+sma[i]*huge[m-1-i]%mod+mod)%mod;
            }
            if(p%block==0)
            {
                lim=1,l=0;
                while(lim<=(t+len))
                {
                    lim<<=1,++l;
                }
                for(int i=t+1;i<=lim;i++)
                {
                    sma[i]=0;
                }
                for(int i=0;i<=lim;i++)
                {
                    r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
                }
                NTT(sma,1),NTT(huge,1);
                for(int i=0;i<=lim;i++)
                {
                    huge[i]=huge[i]*sma[i]%mod;
                }
                NTT(huge,-1);
                int ny=ksm(lim,mod-2);
                for(int i=0;i<=lim;i++)
                {
                    huge[i]=huge[i]*ny%mod;
                }
                len=(len+t);
                for(int i=len+1;i<=lim;i++)
                {
                    huge[i]=0;
                }
            }
        }
    }
    int ans=1;
    for(int i=1;i<=n;i++)
    {
        Q[i]=(Q[i-1]-(ans*q[i])%mod+mod);
        ans=(ans-(q[i]*k[i-1])%mod+mod)%mod;
        Q[i]%=mod;
        cout<<Q[i]<<"\n";
    }
    return 0;
}

chevron_left 退役记
CF662C Binary Table chevron_right

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名