yukicoder : No.801 エレベーター

久々に時間通り参加、途中離脱。でもEは時間あっても思いつけてなさそうだった。
https://yukicoder.me/problems/no/801

問題

N階建のビルがあり、プレイヤーは初期状態で1階にいる。
このビルにはM個のエレベーターがあり、それぞれL[i]～R[i]階の間を運航する。

プレイヤーは、自身のいる階にエレベータがあるとき、どれかを選択して乗り込み、そのエレベーターの運行範囲のいずれかで降りる。
（エレベーターが無いときは移動しない）

K回上記処理を行うときの移動経路は何通りか。
なお、同じ階の移動を行う場合でもエレベーターが異なれば経路は異なるとみなす。

解法

f(n,k) := n回エレベータに載った状態で、k階にいるような経路の組み合わせ
とする。
今(n+1)回目の移動でi番のエレベータを使うとする。
その場合、移動元の組み合わせはsum(f(n,L[i])～f(n,R[i]))であり、その値がf(n+1,L[i])～f(n+1,R[i])に加算される。
前者のsumの処理も、後者の範囲加算も累積和を使えば1回O(N+M)で行えるので、全体でO((N+M)K)で解ける。

int N,M,K;
int L[3030],R[3030];
ll mo=1000000007;
ll from[3030];
ll to[3030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	FOR(i,M) cin>>L[i]>>R[i];
	
	from[1]=1;
	FOR(i,K) {
		ZERO(to);
		FOR(x,N+1) if(x) (from[x]+=from[x-1])%=mo;
		
		FOR(x,M) {
			ll sum=(from[R[x]]-from[L[x]-1]+mo)%mo;
			(to[L[x]]+=sum)%=mo;
			(to[R[x]+1]+=mo-sum)%=mo;
		}
		
		FOR(x,N+1) (to[x+1]+=to[x])%=mo;
		swap(from,to);
	}
	
	cout<<from[N]<<endl;
	
	
}

まとめ

ここまでは順調でした。