AtCoder ARC #219 : B - Reverse Permutation

一見びっくりするけど実は単純。
https://atcoder.jp/contests/arc219/tasks/arc219_b

問題

1～Nの順列Qに対し、Q'は１か所の部分列を反転させてできる数列のうち辞書順最小のものを示す。
1～Nの順列Pが与えられる。Q'=PとなるQは何通りか。

解法

Pのprefixのうち、(1,2,3...)と一致するのが最大L要素とする。
もしQのうち(1,2,...)と一致するのが最大M要素の時、Q[M+1]!=M+1なところをQ[M+1]=M+1にする。
その際、元々M+1のあった場所の候補は(N-M-2)通りである。
よってMを総当たりして(N-M-2)の総和を取ればよい。

int T,N;
int P[505050];
const ll mo=998244353;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) {
			cin>>P[i];
			P[i]--;
		}
		ll ret=0;
		FOR(i,N) {
			if(P[i]!=i) break;
			ret+=N-1-i;
		}
		if(i==N) ret++;
		cout<<ret%mo<<endl;
	}
}

まとめ

まぁ400ptなのでこんな感じか。