Codeforces - 474D - Flowers

Question

题目大意

Marmot 吃花，两种颜色红 R 和白 W，每次吃白花 W 都只能一次连续吃 k 朵，问在花的个数从 a 到 b ( [a, b] ) 范围里，总共有多少种吃法。

解析

这题没有想出来，其实不难，一开始想到了前 [0，k) 肯定是 1 ，即 dp[0 ~ k-1] = 1 ，且 dp[k] = 2 ，但最后却没有想到 dp[i] 求法；

dp[i] 有两种来头:

• dp[i-1] 上添加一朵红花；
• dp[i-k] 上条件 k 朵白花；

所以 dp[i] = dp[i-1] + dp[i-k] 。

然后就是处理求和了，有一个要注意的地方，最后输出答案的时候，要注意输出是 (mod + sums[r] - sums[l-1])%mod ，因为如果上面取模其中， sum[l-1] < mod 且比较大，但 sum[r] > mod ，取模之后 sum[r] < sum[l] ，所以要先加上 mod 。

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {

    public static final long mod = 1000000007;
    public static final int MAX = 100005;

    public static void main(String[] args){
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        int t = cin.nextInt();
        int k = cin.nextInt();
        long[] dp = new long[MAX];
        long[] sums = new long[MAX];
        sums[0] = 0;
        for(int i = 1; i < k; i++){
            dp[i] = 1;
            sums[i] = (dp[i]%mod + sums[i-1]%mod)%mod;
        }
        dp[k] = 2;
        sums[k] = (dp[k]%mod + sums[k-1]%mod)%mod;
        for(int i = k+1; i < MAX; i++) {
            dp[i] = (dp[i-1]%mod + dp[i-k]%mod)%mod;
            sums[i] = (sums[i-1]%mod + dp[i]%mod)%mod;
        }
        for(int i = 0; i < t; i++){
            int l = cin.nextInt();
            int r = cin.nextInt();
//            System.out.println(sums[r] - sums[l-1]);  //err
//            System.out.println( (sums[r] - sums[l-1])%mod); //err
            System.out.println( (mod + sums[r] - sums[l-1])%mod);
        }
    }
}