专栏文章

题解：P11754 [COCI 2024/2025 #5] 绘图 / Crtež

zzxdjmq
P11754题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mipzpwuj
此快照首次捕获于
2025/12/03 20:35
3 个月前
此快照最后确认于
2025/12/03 20:35
3 个月前
查看原文

P11754 [COCI 2024/2025 #5] 绘图 / Crtež

更好的阅读体验：本人的博客园

解法说明

题面复杂程度可以说是非常诈骗。本题代码难度不高，难度主要在理解题面。
无论如何操作，初始序列都是由 −1-1 间隔开的 00 的连续段。
根据操作说明，我们可以知道两个 00 的连续段不会互相影响，并且要求的是互不等价的最终序列的方案数，所以根据乘法原理，总方案数就是各个连续段方案数之积。
但是这个也很难求，可以手模一下找规律。设连续段长度为 ll。
l=1l=1 时，有 33 种方案：[0],[−1],[1][0],[-1],[1]；
l=2l=2 时，有 99 种方案：[−1,−1],[−1,0],[−1,1],[0,−1],[0,0],[1,−1],[1,0],[1,1],[1,2][-1,-1],[-1,0],[-1,1],[0,-1],[0,0],[1,-1],[1,0],[1,1],[1,2]。
聪明的你一定已经发现了规律并通过第三个样例验证了该规律：长为 ll 的连续段的方案数为 3l3^l。
当然还有另一种找规律方法：dp
设 dpi,0/1/2/3dp_{i,0/1/2/3} 表示第 ii 位分别为 −1-1，00，新数字，上一位填的数字的方案数。
则可以得到转移方程：
{dpi,0=dpi−1,0+dpi−1,1+dpi−1,2+dpi−1,3dpi,1=dpi−1,0+dpi−1,1+dpi−1,2+dpi−1,3dpi,2=dpi−1,0+dpi−1,2+dpi−1,3dpi,3=dpi−1,2+dpi−1,3\begin{cases} dp_{i,0}=dp_{i-1,0}+dp_{i-1,1}+dp_{i-1,2}+dp_{i-1,3}\\ dp_{i,1}=dp_{i-1,0}+dp_{i-1,1}+dp_{i-1,2}+dp_{i-1,3}\\ dp_{i,2}=dp_{i-1,0}+dp_{i-1,2}+dp_{i-1,3}\\ dp_{i,3}=dp_{i-1,2}+dp_{i-1,3} \end{cases}
总方案数为四情况之和，容易发现总方案数都是 3i3^i。
综上，最终解法即为维护当前 00 的数量 tt 并输出 3t3^t 即可，此处使用动态开点线段树，空间卡的比较死。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define int long long
#define mid ((l+r)>>1)
const int N=1e6+10,qq=1e5+10,mod=1e9+7;

int n,Q;

il int qpow(int x,int y){
    int res=1;
    while(y){
        if(y&1)res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res;
}

// 动态开点线段树
struct Segment_Tree{
    int t[qq<<8];
    signed ls[qq<<8],rs[qq<<8];
    bool lz[qq<<8];
    int cnt=1;
    il void pu(int nw){
        t[nw]=t[ls[nw]]+t[rs[nw]];
    }
    il void pd(int l,int r,int nw){
        if(lz[nw]){
            if(!ls[nw])ls[nw]=++cnt;
            if(!rs[nw])rs[nw]=++cnt;
            t[ls[nw]]=(mid-l+1)-t[ls[nw]];
            t[rs[nw]]=(r-mid)-t[rs[nw]];
            lz[ls[nw]]^=1,
            lz[rs[nw]]^=1;
            lz[nw]=0;
        }
    }
    void modify(int l,int r,int S,int T,int nw){
        if(S<=l && r<=T){
            t[nw]=(r-l+1)-t[nw];
            lz[nw]^=1;
            return;
        }
        pd(l,r,nw);
        if(mid>=S){
            if(!ls[nw])ls[nw]=++cnt;
            modify(l,mid,S,T,ls[nw]);
        }
        if(mid<T){
            if(!rs[nw])rs[nw]=++cnt;
            modify(mid+1,r,S,T,rs[nw]);
        }
        pu(nw);
    }
}t;

//求总和直接t.t[1]即可。

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin>>n>>Q;
    while(Q--){
        int l,r;
        cin>>l>>r;
        t.modify(1,n,l,r,1);
        cout<<qpow(3,n-t.t[1])<<'\n';
    }
    return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...