AtCoder ARC #194 : D - Reverse Brackets

これは割とすんなり。
https://atcoder.jp/contests/arc194/tasks/arc194_d

問題

N文字の正しい括弧列Sが与えられる。
このうち、正しい括弧列をなす部分列を選択し、前後を反転したうえで"("と")"を逆にする手順を任意回数行えるとする。
これにより構築できる括弧列は何通りか。

解法

f(S) := 正しい括弧列Sに対し、構築できる括弧列の数
今見ている部分列が、S=ABCD...という形を成しているとする。
A,B,C,D....は、それ以上分割できない(分割すると正しい括弧列ではなくなってしまう)括弧列とする。
すると、A,B,C,D...は互いに入れ替えることができる。

この時、
f(S) = f(A)*f(B)*f(C)...*g(ABCD...)
g(ABCD...) := ABCD...のうち同じ並びの文字列にできる部分列を同一視した場合の並び順
のように表現できるので、再帰的に算出しよう。
同じ並びの文字列にできるかどうかは、木を成すグラフの同一判定ができればよいので、ハッシュを使い行うことができる。

int N;
string S;
const ll mo=998244353;
const int NUM_=2000003;

static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];

const int prime_max = 1010101;
vector<int> prime;
int NP,divp[prime_max];
int src;
void cprime() {
	if(NP) return;
	for(int i=2;i<prime_max;i++) if(divp[i]==0) {
		//M[i]=NP;
		prime.push_back(i); NP++;
		for(ll j=1LL*i*i;j>=i&&j<prime_max;j+=i) if(divp[j]==0) divp[j]=i;
	}
}

pair<ll,ll> hoge(int L,int R) {
	ll mul=1;
	map<ll,int> M;
	int tot=0;
	vector<ll> cand;
	if(L==R) {
		return {1,1};
	}
	int pre=L;
	int cur=0;
	int i;
	for(i=L;i<R;i++) {
		if(S[i]=='(') cur++;
		else if(S[i]==')') cur--;
		if(cur==0) {
			auto p=hoge(pre+1,i);
			pre=i+1;
			mul=mul*p.first%mo;
			M[p.second]++;
			tot++;
			cand.push_back(p.second);
		}
	}
	
	
	sort(ALL(cand));
	ll hash=1;
	FOR(i,cand.size()) hash=hash*(cand[i]+prime[i]+src)%mo;
	(mul*=fact[tot])%=mo;
	FORR2(a,b,M) (mul*=factr[b])%=mo;
	
	return {mul,hash};
	
	
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cprime();
	src=rand()%101010+101;

	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>>N>>S;
	auto p=hoge(0,N);
	cout<<p.first<<endl;
}

まとめ

最初これO(NlogN)かな…？と思ったけど、自分のコードはO(N^2)かかってるな。