[ZJOI2019]开关

客官°小女子只卖身不卖艺 2021-12-23 15:13 376阅读 0赞

[\[ZJOI2019\]开关][ZJOI2019]

[题解][Link 1]

到了就停止，很麻烦，因为要状压

走了i步，还没有停止方案数，再除以概率，还是不行，还要状压

所以干脆反演（容斥？）直接求i步之后停止的概率，不管之前有没有停止，然后进行反演

概率生成函数

1.每个开关的EGF

OGF：j开关的x^i的系数定义为：操作了i次，都操作到了j，并且到达了目标状态的概率

EGF：额外除以i!，为了之后多重集合排列用，可以直接用e代替

2.总共的EGF

直接把每个EGF乘起来

这一步可以背包得到e^(ix)的系数a

3.反演，

要求的生成函数OGF是h，这样h'(1)就是答案

而g\*h=f，h=f/g

g就是si=0的状态下的OGF（等价于绕环）

EGF和OGF的转化？就是每一位乘上i!

把e麦克劳林展开，直接乘上i！即可

![1399631-20190515172918115-1927959338.png][]

![1399631-20190515172956036-1174799823.png][]

计算h'(1)要用到f'(1),g'(1),f(1),g(1)

但是可能1-vx=0

4.通分消掉分母，求导后带入1

通分，分子分母同时干掉自己的分母

![1399631-20190515173103044-433687966.png][]

A(x),C(x)都是知道的

带入1

前缀后缀积，

前缀后缀求导dp，枚举当前的(1-vx)导不导

或者发现带入1，1-x是0，可以直接对v=1特殊处理，别的含有(1-x)的连乘积都是0

注意：

多次进入calc

**初值时，滚动数组f\[0\]也要先清空**

#include<bits/stdc++.h>
    #define reg register int
    #define il inline
    #define fi first
    #define se second
    #define mk(a,b) make_pair(a,b)
    #define numb (ch^'0')
    #define pb push_back
    #define solid const auto &
    #define enter cout<<endl
    #define pii pair<int,int>
    using namespace std;
    typedef long long ll;
    template<class T>il void rd(T &x){
        char ch;x=0;bool fl=false;
        while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
        for(x=numb;isdigit(ch=getchar());x=x*10+numb);
        (fl==true)&&(x=-x);
    }
    template<class T>il void output(T x){
        if(x/10)output(x/10);putchar(x%10+'0');}
    template<class T>il void ot(T x){
        if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}
    template<class T>il void prt(T a[],int st,int nd){
        for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}
    
    namespace Miracle{
    const int N=100+5;
    const int M=5e4+5;
    const int NM=5e6+5;
    const int mod=998244353;
    int n,s[N];
    int p[N];
    int ad(int x,int y){
        return (x+y)>=mod?x+y-mod:x+y;
    }
    void inc(int &x,int y){
        x=ad(x,y);
    }
    int mul(int x,int y){
        return (ll)x*y%mod;
    }
    int qm(int x,int y=mod-2){
        int ret=1;while(y){
            if(y&1) ret=mul(ret,x);x=mul(x,x);y>>=1;
        }return ret;
    }
    int f[2][2*M];
    struct po{
        int a,v;
    }t[2*M];
    int pre[2*M],bac[2*M];
    int Pr[2*M],Bc[2*M];
    int tot,iv,iv2;
    pair<int,int>calc(int *s){
        int tmp=0;
        memset(f[tmp],0,sizeof f[tmp]);
        f[tmp][0+tot]=1;
        for(reg i=1;i<=n;++i){
            tmp^=1;
            memset(f[tmp],0,sizeof f[tmp]);
            for(reg j=-tot;j<=tot;++j){
                if(f[tmp^1][j+tot]){
                    int lp=f[tmp^1][j+tot];
                    inc(f[tmp][j+tot+p[i]],mul(iv2,lp));
                    if(s[i]&1){
                        inc(f[tmp][j+tot-p[i]],mod-mul(iv2,lp));
                    }else{
                        inc(f[tmp][j+tot-p[i]],mul(iv2,lp));
                    }
                }
            }
        }
        for(reg i=-tot;i<=tot;++i){
            t[i+tot].a=f[tmp][i+tot];
            t[i+tot].v=mul(ad(mod,i),iv);
    
            // cout<<" i "<<i<<" a "<<t[i+tot].a<<" v "<<t[i+tot].v<<endl;
    
            if(i!=-tot) pre[i+tot]=mul(pre[i+tot-1],ad(1,mod-t[i+tot].v));
            else pre[i+tot]=ad(1,mod-t[i+tot].v);
            
            if(i!=-tot) Pr[i+tot]=ad(mul(Pr[i+tot-1],ad(1,mod-t[i+tot].v)),mul(pre[i+tot-1],mod-t[i+tot].v));
            else Pr[i+tot]=mod-t[i+tot].v;
        }
        for(reg i=tot;i>=-tot;--i){
            int v=t[i+tot].v;
            int now=i+tot;
            if(i!=tot) bac[now]=mul(bac[now+1],ad(1,mod-v));
            else bac[now]=ad(1,mod-v);
    
            if(i!=tot) Bc[now]=ad(mul(Bc[now+1],ad(1,mod-v)),mul(bac[now+1],mod-v));
            else Bc[now]=mod-v;
        }
        
        // prt(pre,0,tot+tot);
        // prt(bac,0,tot+tot);
    
        pii ret;ret.fi=ret.se=0;
        for(reg i=-tot;i<=tot;++i){
            int a=t[i+tot].a;
            int tmp=t[i+tot].a;
            if(i!=-tot) tmp=mul(tmp,pre[i+tot-1]);
            if(i!=tot) tmp=mul(tmp,bac[i+tot+1]);
            ret.fi=ad(ret.fi,tmp);
    
            tmp=0;
            int now=i+tot;
            if(i==-tot){
                tmp=mul(a,Bc[now+1]);
            }else if(i==tot){
                tmp=mul(a,Pr[now-1]);
            }else{
                tmp=ad(mul(mul(pre[now-1],a),Bc[now+1]),mul(mul(bac[now+1],a),Pr[now-1]));
            }
            ret.se=ad(ret.se,tmp);
        }
        // cout<<" ret "<<ret.fi<<" "<<ret.se<<endl;
        return ret;
    }
    int main(){
        rd(n);
        for(reg i=1;i<=n;++i) rd(s[i]);
        for(reg i=1;i<=n;++i) rd(p[i]),tot=ad(tot,p[i]);
        iv=qm(tot);
        iv2=qm(2); 
        
        pii A=calc(s);
        // cout<<endl<<endl;
       memset(s,0,sizeof s);
        pii C=calc(s);
        ll ans=mul(ad(mul(A.se,C.fi),mod-mul(A.fi,C.se)),qm(mul(C.fi,C.fi)));
        ot(ans);
        return 0;
    }
    
    }
    signed main(){
        Miracle::main();
        return 0;
    }
    
    /*
       Author: *Miracle*
    */

转载于:https://www.cnblogs.com/Miracevin/p/10865003.html

[ZJOI2019]: https://www.luogu.org/problemnew/show/P5326
[Link 1]: https://blog.csdn.net/alan_cty/article/details/89710456
[1399631-20190515172918115-1927959338.png]: /images/20211223/9c639396eb2c40f6a32e9e50f30afab8.png
[1399631-20190515172956036-1174799823.png]: /images/20211223/2107269d0f4e41c4a18e175d8042a50f.png
[1399631-20190515173103044-433687966.png]: /images/20211223/f7c401dac63944ce92e3a5a7e2ced343.png