题解：P11754 [COCI 2024/2025 #5] 绘图 / Crtež
zxdjmq
·
·
题解
P11754 [COCI 2024/2025 #5] 绘图 / Crtež
更好的阅读体验：本人的博客园
解法说明
题面复杂程度可以说是非常诈骗。本题代码难度不高，难度主要在理解题面。
无论如何操作，初始序列都是由 -1 间隔开的 0 的连续段。
根据操作说明，我们可以知道两个 0 的连续段不会互相影响，并且要求的是互不等价的最终序列的方案数，所以根据乘法原理，总方案数就是各个连续段方案数之积。
但是这个也很难求，可以手模一下找规律。设连续段长度为 l。
$l=2$ 时，有 $9$ 种方案：$[-1,-1],[-1,0],[-1,1],[0,-1],[0,0],[1,-1],[1,0],[1,1],[1,2]$。
聪明的你一定已经发现了规律并通过第三个样例验证了该规律：长为 $l$ 的连续段的方案数为 $3^l$。
当然还有另一种找规律方法：dp
设 $dp_{i,0/1/2/3}$ 表示第 $i$ 位分别为 $-1$，$0$，新数字，上一位填的数字的方案数。
则可以得到转移方程：
$$
\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}
$$
总方案数为四情况之和，容易发现总方案数都是 $3^i$。
综上，最终解法即为维护当前 $0$ 的数量 $t$ 并输出 $3^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;
}
```