Codeforces #274, Division 1, C ( Division 2, E ) : Riding in a Lift

問題文

　http://codeforces.com/contest/480/problem/C

問題概要

　 階ある建物のエレベーターで遊ぶ。プレイヤーは最初 階にいて、 階に行くことはできない。また、 階から 階に移動するとき、 かつ でなければならない。このルールを守って 回移動するとき、移動方法は何通りあるか、modulo で求めよ。
　
　

解法

　いかにも答えが大きくなるので、同一視できる状態を探して動的計画法で計算時間を削減します。移動回数は必須として、ある移動が valid か否かを判定するためには現在位置が必要になるので、次のような状態の取り方の DP が思い付きます。

• dp[ i 階移動した ][ j 階にいる ] := 移動の総数

これだと状態数のオーダは になりますが、各状態から次の移動を一つずつ試すと 時間かかって TLE してしまいます。何らかの手段で更に計算時間を削る必要があります。
　ところで、現在地点 を固定したとき、移動可能かどうかを決める不等式（問題文参照）の右辺 は定数になります。この値を とすると、 階から移動できる階 は区間 内の階となります。この区間に（ Segment Tree で）暫定解を足し込むことで 時間にできますが、 であることを考えるとまだちょっと不安です。
　今までは所謂「配る DP」で考えてきましたが、「貰う DP」にしてみるとどうでしょうか。移動先の階 を固定したとき、 としてありえる範囲は と の位置関係によって決まります。 を挟んで の反対側にある階からは、どの階からでも に来れます。 と同じ方向の階は、 と の中間点の手前までです。ということで、貰う DP で考えた場合も遷移元となり得る階は連続した区間になっています（同じ階からの移動はできないので正確には区間は二つ）。区間の和は、予め 時間かけて累積和を計算しておくことで 時間で計算できます。累積和の計算はそれぞれの移動回数に対して一回ずつでよいので、DP 全体を 時間で処理できるようになります。これで がとれて安心できるオーダになりました。

コード

using LL = long long; using ULL = unsigned long long;
using VI = vector<int>; using VVI = vector<VI>;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define ALL( c ) (c).begin(), (c).end()

constexpr int MOD = 1000000007;

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n, a, b, K;
	cin >> n >> a >> b >> K;
	--a, --b;

	VVI dp( K + 1, VI( n, 0 ) );
	dp[0][a] = 1;

	REP( i, 1, K + 1 )
	{
		VI csum( 1, 0 );
		partial_sum( ALL( dp[ i - 1 ] ), back_inserter( csum ), []( const int s, const int t ){ return ( s + t ) % MOD; } );

		REP( k, 0, n )
		{
			if ( k == b )
			{
				continue;
			}

			const int d = abs( b - k );
			const int md = ( d - 1 ) / 2;

			const int l = max(     0, b < k ? k - md :     0 );
			const int r = min( n - 1, k < b ? k + md : n - 1 );

			LL s = 0;
			if ( k )
			{
				( s += csum[k] - csum[l] + MOD ) %= MOD;
			}
			if ( k + 1 < n )
			{
				( s += csum[ r + 1 ] - csum[ k + 1 ] + MOD ) %= MOD;
			}

			if ( !s )
			{
				continue;
			}
			while ( s < 0 )
			{
				s += MOD;
			}
			( dp[i][k] += s ) %= MOD;
		}
	}

	const LL res = accumulate( ALL( dp[K] ), 0LL ) % MOD;
	cout << res << endl;

	return 0;
}