Codeforces #271, D : Flowers

問題文

　http://codeforces.com/contest/474/problem/D

問題概要

　'W', 'R' からなる文字列であって、出現する全ての 'W' を互いに交差しない、連続した長さ の区間に分割できるものについて考える。
　以下の形式のクエリを 件処理せよ。

• 二つの整数 が与えられる。長さが 以上 以下であり、上記の性質を満たす文字列の総数を MOD で求めよ。

　

解法

　クエリの個数がそれなりに多いので、かなり高速に処理しなければなりません。同じクエリに対する答えは常に不変であるので、クエリの答えを全て前計算できれば、各クエリを定数時間で処理することができます。このとき、 の答えは の答えから の答えを引くことで求められることに注意すると、次のような動的計画法＋累積和により答えを前計算できます。

• dp[ i 文字並べた ] := 総数

文字列の末尾に文字を付け加えていくと考えると dp[ i ] からの遷移は 2 通りで、

• 'R' を付け足す : dp[ i + 1 ] を更新
• 'W' を付け足す : dp[ i + k ] を更新

となります。この計算が終わった後、DP テーブルの累積和を取れば、各 に関して の答えが求まります。
　あとは、各クエリに対し適当に差分を求めて出力すれば、Time Limit 以内で問題を解くことができます。

コード

using VI = vector<int>; using VVI = vector<VI>;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

constexpr int MAX_B = 100000;
constexpr int MOD = 1000000007;

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

	int t, k;
	cin >> t >> k;

	VI dp( MAX_B + 1 );
	dp[0] = 1;

	REP( i, 0, MAX_B )
	{
		( dp[ i + 1 ] += dp[i] ) %= MOD;
		if ( i + k <= MAX_B )
		{
			( dp[ i + k ] += dp[i] ) %= MOD;
		}
	}

	VI csum( 1, 0 );
	partial_sum( dp.begin() + 1, dp.end(), back_inserter( csum ), []( const int s, const int a ){ return ( s + a ) % MOD; } );

	REP( i, 0, t )
	{
		int a, b;
		cin >> a >> b;
		cout << ( csum[b] - csum[ a - 1 ] + MOD ) % MOD << endl;
	}

	return 0;
}