Codeforces #997 : Div2 E. Nested Segments

これはすんなり。
https://codeforces.com/contest/2056/problem/E

問題

Nマスがあり、そこにM個の区間が与えられる。
各区間の対は、以下のいずれかを満たす。

• 共通部分を持たない。
• 共通部分を持つ場合、片方に片方が完全に内包される。

条件を満たすように、極力多くの区間を加えたい場合、加え方は何通りか。

解法

区間の包含関係を木構造で示す。
すると、各ノード内に対応するマスの数が計算できる。
そのマス数をnとすると、区間をn個置くことができ、それはカタラン数C(n)に一致する。
よってそれらのカタラン数の積を取ろう。

ll mo=998244353;
const int NUM_=400001;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];

vector<int> E[202020];

int T,N,M;

ll catalan(int n) {
	return fact[2*n]*factr[n]%mo*factr[n+1]%mo;
}

ll hoge(int L,int R) {
	
	int num=0;
	ll ret=1;
	while(L<R) {
		num++;
		if(E[L].empty()) {
			L++;
		}
		else {
			int x=E[L].back();
			E[L].pop_back();
			ret=ret*hoge(L,x)%mo;
			L=x;
		}
	}
	return ret*catalan(num-1)%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;

	inv[1]=fact[0]=factr[0]=1;
	for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
	for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	
	cin>>T;
	while(T--) {
		cin>>N>>M;
		FOR(i,N+1) E[i].clear();
		FOR(i,M) {
			cin>>x>>y;
			E[x-1].push_back(y);
		}
		FOR(i,N) sort(ALL(E[i]));
		cout<<hoge(0,N)<<endl;
	}

}

まとめ

区間の問題でカタラン数が出てくる…と思ったけど、区間に対応する括弧列を考えればそんなもんか。