[ARC206C] Tree Sequence 题解

FFTotoro · 2025-09-29 22:25:36 · 题解

简单找性质题。

对于所有区间这个限制很严格，尝试放松限制。考察区间长度 =2，即对于 A_i,A_{i+1} 两个数，条件等价于 A_i=i+1\lor A_{i+1}=i，其中 \lor 表示析取，即只需要满足两个条件中的一个。发现只要长度 =2 的条件满足了，所有条件自然地就满足了——每相邻两个元素之间都有一条边，一段长度为 k 的区间就会被一条长度为 k-1 的链连起来。

于是就可以 DP 了：设 f_{i,0/1} 表示当前考虑了前 i 个元素，是否满足 A_i=i+1。f_{i-1}\to f_i 时只要对于 i，两个条件满足一个就可以转移。转移系数的推导是简单的，具体可以参考代码。时间复杂度 O(n)。

代码中的数组是 0-indexed 的。

放代码：

#include<bits/stdc++.h>
using namespace std;
const int P=998244353;
inline int add(int x,int y){
  int s=x+y; if(s>=P)s-=P; return s;
}
inline void self_add(int &x,int y){
  if((x+=y)>=P)x-=P;
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n; cin>>n;
  vector<int> a(n);
  for(auto &i:a)cin>>i,i-=i>0;
  vector<int> f(2); f[1]=1;
  for(int i=0;i<n;i++){
    vector<int> g(2);
    if(~a[i]){
      if(a[i]==i-1)self_add(g[0],add(f[0],f[1]));
      // 往前满足条件
      else if(a[i]==i+1)self_add(g[1],f[1]);
      // 往后满足条件
      else self_add(g[0],f[1]);
      // 上一个元素往后的条件必须满足，这个元素往前后的条件都一定不满足
    } // a[i] 的值确定
    else{
      // 类似于前面，只是每种转移多了一个系数
      if(i)self_add(g[0],add(f[0],f[1]));
      self_add(g[0],1ll*f[1]*(n-((bool)i)-(i<n-1))%P);
      if(i+1<n)self_add(g[1],f[1]);
    } // a[i] 的值可以随便选
    f=move(g);
  }
  cout<<add(f[0],f[1])<<endl;
  return 0;
}