F

考虑暴力 dp，设计如下 dp 状态：

$f_{i,0}$ 代表考虑到第 $i$ 个，第 $i$ 个是妖精的方案数；
$f_{i,1}$ 代表考虑到第 $i$ 个，第 $i$ 个是兔子，第 $i+1$ 个没有限制的方案数；
$f_{i,2}$ 代表考虑到第 $i$ 个，第 $i$ 个是兔子，第 $i+1$ 个也是兔子的方案数。

转移若 $i+1$ 能填 $1$ 则有 $f_{i,0}+f_{i,1}+f_{i,2} \to f_{i+1,2}$ ，能填 $2$ 则有 $f_{i,1}+f_{i,2} \to f_{i+1,1}$ ，能填 $3$ 则有 $f_{i,0}+f_{i,1} \to f_{i+1,0}$ 。

最终答案是 $f_{n,0}+f_{n,1}$ ，因为显然终态不能带限制。

f[x-1][0]=1,f[x-1][1]=f[x-1][2]=0;
for(int i=x;i<=y;i++){
	f[i][0]=f[i][1]=f[i][2]=0;
	if(a[i]==0||a[i]==1) add(f[i][2],f[i-1][0]),add(f[i][2],f[i-1][1]),add(f[i][2],f[i-1][2]);
	if(a[i]==0||a[i]==2) add(f[i][1],f[i-1][1]),add(f[i][1],f[i-1][2]);
	if(a[i]==0||a[i]==3) add(f[i][0],f[i-1][0]),add(f[i][0],f[i-1][1]);
}
cout<<(f[y][0]+f[y][1])%mod<<endl;

然后考虑优化这个 dp，将状态转移写成矩阵的形式，那么我们有：

$\begin{bmatrix} f_{i,0} & f_{i,1} & f_{i,2} \end{bmatrix} \times \begin{bmatrix} [a_{i+1}=0 \lor a_{i+1}=3] & 0 & [a_{i+1}=0 \lor a_{i+1}=1] \\ [a_{i+1}=0 \lor a_{i+1}=3] & [a_{i+1}=0 \lor a_{i+1}=2] & [a_{i+1}=0 \lor a_{i+1}=1] \\ 0 & [a_{i+1}=0 \lor a_{i+1}=2] & [a_{i+1}=0 \lor a_{i+1}=1] \end{bmatrix} = \begin{bmatrix} f_{i+1,0} & f_{i+1,1} & f_{i+1,2} \end{bmatrix}$

线段树维护矩阵乘法即可，时间复杂度 $O(k^3q\log n)$ ，本题中 $k=3$ 。

Mat getm(int x){
    Mat mat;
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++) mat.a[i][j]=0;
    }
    if(x==0||x==3) mat.a[0][0]=mat.a[1][0]=1;
    if(x==0||x==2) mat.a[1][1]=mat.a[2][1]=1;
    if(x==0||x==1) mat.a[0][2]=mat.a[1][2]=mat.a[2][2]=1;
    return mat;
}
struct SGT{
    node tr[maxn*4];
    void pushup(int u){
        if(tr[u].l==tr[u].r) return ;
        tr[u].x=tr[ls(u)].x*tr[rs(u)].x;
    }
    void build(int u,int l,int r,int *a){
        tr[u].l=l,tr[u].r=r;
        if(l==r) return tr[u].x=getm(a[l]),void();
        int mid=(l+r)>>1;
        build(ls(u),l,mid,a),build(rs(u),mid+1,r,a),pushup(u);
    }
    void upd(int u,int x,int k){
        if(tr[u].l==tr[u].r) return tr[u].x=getm(k),void();
        int mid=(tr[u].l+tr[u].r)>>1;
        if(x<=mid) upd(ls(u),x,k);
        else upd(rs(u),x,k);
        pushup(u);
    }
    Mat query(int u,int l,int r){
        if(ir(l,r,tr[u].l,tr[u].r)) return tr[u].x;
        else if(!ofr(l,r,tr[u].l,tr[u].r)) return query(ls(u),l,r)*query(rs(u),l,r);
        else return I;
    }
}sgt;
void solve(){
    n=read<int>(),m=read<int>();
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++) I.a[i][j]=(i==j);
    }
    for(int i=1;i<=n;i++) a[i]=read<int>();
    sgt.build(1,1,n,a);
    while(m--){
        int op=read<int>(),x=read<int>(),y=read<int>();
        if(op==1) sgt.upd(1,x,y);
        else{
            Mat A=sgt.query(1,x,y);
            // for(int i=0;i<3;i++,cout<<endl){
            //     for(int j=0;j<3;j++) cout<<A.a[i][j]<<" ";
            // }
            print((A.a[0][0]+A.a[0][1])%mod,'\n');
        }
    }
}

牛客挑战赛83 F 题解

F