Codeforces #271 Div2 D. Flowers

気づいてしまえばあっさり。
http://codeforces.com/contest/474/problem/D

問題

赤と白の花を１列に並べる。
その際、ただし、白い花はK個単位でしか並べられない。

ここで、以下のクエリT個に答えよ。

• A[i]、B[i]が与えられるので、条件を見たしA[i]～B[i]個のいずれか花を並べる並べ方を答えよ。

解法

B[i]の上限は10^5なので、先にx個の花の並べ方を1～10^5まで列挙し、その累積和を求めておけば、各クエリにO(1)で回答できる。
x個の花の並べ方は、(x-1)の花に赤い花を１個加えるケースと、(x-K)個の花に白い花をK個並べる場合があるので、単純なDPで済む。

int T,K;
ll num[100300];
ll R[100300];
ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T>>K;
	FOR(i,K) num[i]=1;
	for(i=K;i<=100000;i++) num[i]=(num[i-1]+num[i-K])%mo;
	
	FOR(i,100020) R[i+1]=(R[i]+num[i])%mo;
	
	FOR(i,T) {
		cin>>x>>y;
		ll tot=R[y+1]-R[x];
		cout << ((tot%mo)+mo)%mo << endl;
	}
}

まとめ

最初無駄にCombinationとか考えて時間を消費してしまった。
それを除けばCよりDの方が簡単だね。