Google Code Jam 2021 Round 2 : C. Hidden Pancakes

これは何とか解けてよかった。
https://codingcompetitions.withgoogle.com/codejam/round/0000000000435915/00000000007dc20c

問題

半径1～Nのパンケーキが1枚ずつ重なっている。
下のn枚を上から見たとき、V[n]枚分が見えるものとする。
条件を満たすパンケーキの重ね順は何通りか。

解法

f(L,R) := 区間[L,R]内における条件を満たす並べ方
とする。求めたいのはf(1,N)である。

まず区間内最大のパンケーキを求めよう。
これはV[M]=1となる最大のMである。
最大のパンケーキが求まると、それより下のパンケーキと上のパンケーキは独立に考えることができる。
すなわちf(L,R) = f(L,M-1)*f(M+1,R)*Comb(R-L,M-L)である。
なお、f(M+1,R)を計算するときは、区間内のV[x]をM枚目の分の影響を排除するためデクリメントしておこう(下記コードでは、V[x]をデクリメントする代わりに次に探すべきV[M]の値をインクリメントしている)

int N;
int V[101010];
const ll mo=1000000007;
set<int> VS[101010];

ll comb(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		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;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

ll dfs(int L,int R,int cur) {
	if(L==R+1) return 1;
	if(VS[cur].empty()) return 0;
	
	auto it=VS[cur].lower_bound(R+1);
	if(it==VS[cur].begin()) return 0;
	it--;
	int M=*it;
	if(M<L||M>R) return 0;
	ll pat1=dfs(L,M-1,cur);
	ll pat2=dfs(M+1,R,cur+1);
	
	ll ret=pat1*pat2%mo*comb(R-L,M-L)%mo;
	return ret;
	
}


void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	FOR(i,N+1) VS[i].clear();
	
	cin>>N;
	FOR(i,N) {
		cin>>V[i+1];
		VS[V[i+1]].insert(i+1);
	}
	
	ll ret=dfs(1,N,1);
	
	_P("Case #%d: %lld\n",_loop,ret);
}

解法

最初smallだけ通る解をSubmitしたけど、遠回りだったな。