AtCoder ARC #206 : C - Tree Sequence

結構手間取ってしまった。
https://atcoder.jp/contests/arc206/tasks/arc206_c

問題

各要素1～Nの値を取れるN要素の整数列Bが、良い数列であるとは以下を満たすものである。

• Bの各部分列B[L...R]について以下を満たす。
  • L≦v≦Rに対応するR-L+1点のグラフを考える。1要素を除いて、点xと点B[x]を辺で結んだ時、それが木を成すことができる。

今N要素の整数列Aが与えられる。
Aの一部は不定である。Aのうち不定の部分に1～Nのいずれかを入れたとき、それが良い数列であるものは何通りか。

解法

1≦v＜N-1について、A[v]=v+1とA[v+1]=vの少なくとも片方は満たさなければならない。
これを踏まえ、
dp(v,b) := A[1...v]までの要素を定めたとき、A[v]=v+1を満たすかどうかが真偽値bと合致する場合の要素の数
として端から順に値を定めて行くとよい。

int N;
int A[202020];
const ll mo=998244353;

ll from[2];
ll to[2];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	A[0]=1;
	A[N+1]=N;
	FOR(i,N) cin>>A[i+1];
	N+=2;
	
	from[1]=1;
	for(i=1;i<N;i++) {
		ZERO(to);
		if(A[i]==-1) {
			(to[0]=from[0]+from[1]*(N-3))%=mo;
			to[1]=from[1];
		}
		else if(A[i]==i-1) {
			(to[0]=from[0]+from[1])%=mo;
		}
		else if(A[i]==i+1) {
			to[1]=from[1];
		}
		else {
			to[0]=from[1];
		}
		swap(from,to);
	}
	
	cout<<(from[0]+from[1])%mo<<endl;
	
}

まとめ

本番はもっと長いコードを書いてしまっていた。