题目链接：点击打开链接

思路：

给定T k表示T组測试数据

每组case [l,r]

有2种物品a b。b物品必须k个连续出现

问摆成一排后物品长度在[l,r]之间的方法数

思路：

dp[i] = dp[i-1]+dp[i-k];

#include <iostream>

#include <cmath>

#include <algorithm>

#include <cstdio>

#include <cstring>

#include <vector>

#include <set>

using namespace std;

typedef long long ll;

template <class T>

inline bool rd(T &ret) {

    char c; int sgn;

    if(c=getchar(),c==EOF) return 0;

    while(c!='-'&&(c<'0'||c>'9')) c=getchar();

    sgn=(c=='-')?-1:1;

    ret=(c=='-')?

0:(c-'0');

    while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');

    ret*=sgn;

    return 1;

}

template <class T>

inline void pt(T x) {

    if (x < 0) {

        x = -x;

        putchar('-');

    }

    if(x>9) pt(x/10);

    putchar(x%10+'0');

}

/////////////////////////

const int N = 100000 + 2;

const int mod = 1000000007;

ll d[N], sum[N];

int main() {

    int cas, K, l, r;

    rd(cas); rd(K);

    d[0] = 1;

    for (int i = 1; i < N; ++i) {

        d[i] = d[i - 1];

        if (i >= K)

            d[i] += d[i - K];

        d[i] %= mod;

    }

    sum[0] = 1;

    for (int i = 1; i < N; ++i) {

        sum[i] = sum[i - 1] + d[i];

        sum[i] %= mod;

    }

    while (cas -- > 0) {

        rd(l); rd(r);

        pt(((sum[r]-sum[l-1]) % mod + mod) % mod);

        putchar('\n');

    }

    return 0;

}