CFR 474 D. Flowers ( DP )

Problem - D - Codeforces
題意：
有兩種食物，白色和紅色，吃的時候是吃一種排列，滿足白色的必須是連續 K 個。多筆詢問 [ l, r ]，輸出吃 [ l, r ] 各長度方案數其和。
解法：
dp[ i ] : 吃 i 個的方案數
dp[ i ] = dp[ i - 1 ] + dp[ i - K ]

const int MAXB = ( int ) 1e5 + 1; // [ a < b ]

int T, K;

void init(){
	cin >> T >> K;
}

vi dp;
vi pdp;

void preprocess(){
	dp = vi( MAXB );
	dp[ 0 ] = 1;
	for( int i = 0; i + 1 < MAXB; ++i ){
		( dp[ i + 1 ] += dp[ i ] ) %= MOD7;
		if( i + K < MAXB )
			( dp[ i + K ] += dp[ i ] ) %= MOD7;
	}
	pdp = vi( MAXB );
	for( int i = 1; i < MAXB; ++i )
		( pdp[ i ] = pdp[ i - 1 ] + dp[ i ] ) %= MOD7;
}

void solve(){
	for( int i = 0; i < T; ++i ){
		int A, B; cin >> A >> B;
		int ans = pdp[ B ] - pdp[ A - 1 ];
		ans %= MOD7, ans += MOD7, ans %= MOD7;
		cout << ans << endl;
	}
}