474D. Flowers

dp, *1700, https://codeforces.com/contest/474/problem/D

We saw the little game Marmot made for Mole's lunch. Now it's Marmot's dinner time and, as we all know, Marmot eats flowers. At every dinner he eats some red and white flowers. Therefore a dinner can be represented as a sequence of several flowers, some of them white and some of them red.

But, for a dinner to be tasty, there is a rule: Marmot wants to eat white flowers only in groups of size k.

Now Marmot wonders in how many ways he can eat between a and b flowers. As the number of ways could be very large, print it modulo $1000000007 (10^{9} + 7)$ .

Input

Input contains several test cases.

The first line contains two integers t and k ( $1 \leq t, k \leq 10^{5}$ ), where t represents the number of test cases.

The next t lines contain two integers $a_{i}$ and $b_{i}$ ( $1 \leq a_{i} \leq b_{i} \leq 10^{5}$ ), describing the i-th test.

Output

Print t lines to the standard output. The i-th line should contain the number of ways in which Marmot can eat between $a_{i}$ and $b_{i}$ flowers at dinner modulo $1000000007 (10^{9} + 7)$ .

Examples

Input

Output

6
5
5

Note

For K = 2 and length 1 Marmot can eat (R).
For K = 2 and length 2 Marmot can eat (RR) and (WW).
For K = 2 and length 3 Marmot can eat (RRR), (RWW) and (WWR).
For K = 2 and length 4 Marmot can eat, for example, (WWWW) or (RWWR), but for example he can't eat (WWWR).

思路：题目本身就是一个普通的“上楼梯”，但是这里不用前缀和来查询会超时

python

MAX = 1000000007
t, k = map(int, input().split())
MOD = int(1e9+7)
MAXN = 100001
dp = [0]*MAXN
s = [0]*MAXN
dp[0] = 1
s[0] = 1
for i in range(1, MAXN):
    if i >= k:
        dp[i] = (dp[i-1]+dp[i-k]) % MOD
    else:
        dp[i] = dp[i-1] % MOD
    s[i] = (s[i-1]+dp[i]) % MOD

for _ in range(t):
    a, b = map(int, input().split())
    print((s[b]-s[a-1]+MOD) % MOD)

https://www.luogu.com.cn/article/fd2jp6qb
看到题面 “当蛋糕数量为x1到x2之间” 的描述，不难想到可以用前缀和刻画这一点，如下
cpp
int sum(int l,int r){
 return (s[r]-s[l-1]+mod)%mod;
}
接下来考虑蛋糕数量为x的时候有多少种吃法：
我们这样考察：x个蛋糕，如果采取办法1吃，那么会剩下x-1个蛋糕，采取方法2则会剩下x-k （这里x>=k，写代码时注意判断）个蛋糕。
记f(x)为吃x个蛋糕的方法数，我们有：
f(x)=f(x-1)+f(x-k) (x>=k)
这，便是dp题的核心：状态转移方程
其他补充：
记得初始化x=0的情况 f[0]=1
取模
结合前缀和处理
CF tutorial:
We can notate each string as a binary string, instead of red and white flowers. A string of this type is good only if every maximal contigous subsequence of "0" has the length divisible by k. We can make dynamic programming this way : $n r_{i}$ = the number of good strings of length i. If the i-th character is "1" then we can have any character before and if the i-th character is "0" we must have another k - 1 "0" characters before, so $n r_{i} = n r_{i - 1} + n r_{i - k}$ for $i \geq k$ and $n r_{i}$ = 1 for $i < k$ . Then we compute the partial sums ( $s u m_{i} = n r_{1} + n r_{2} + . . . + n r_{i}$ ) and for each query the result will be $s u m_{b} - s u m_{a - 1}$ . This solution has the complexity O(maxVal + t), where maxVal is the maximum value of $b_{i}$ .

设 $d p_{i}$ 为吃 $i$ 朵花的方案数，则有 $d p_{0} = 1, d p_{i} = {\begin{cases} d p_{i - 1}, i < k \\ d p_{i - 1} + d p_{i - k}, i \geq k \end{cases}$ ，据此计算即可。可以用前缀和加快区间和查询速度。

在 k 以下的都只能吃红花，只有一种方案，在 k 以上的可以从 i-1 基础上吃一朵红花或从 i-k 基础上吃 k 朵白花。

python

# 成组放置问题
MOD = 1000000007
MAXN = 100001

t, k = map(int, input().split())

f = [0] * MAXN
f[0] = 1
s = [0] * MAXN
for i in range(1, 100001):
    if i >= k:
        f[i] = (f[i-1] + f[i - k]) % MOD
    else:
        f[i] = f[i - 1]
        #f[i] = 1

    s[i] = (s[i - 1] + f[i]) % MOD

for _ in range(t):
    a, b = map(int, input().split())
    print((s[b] - s[a - 1] + MOD) % MOD)

思路：dp，枚举最后一个连续k个白色段所在位置，得到 $f [i] = \sum_{j = 0}^{i - k} f [j]$ ,然后前缀和维护

python

# 高景行 24数学科学学院
P = int(1e9) + 7

def main():
    n = int(1e5)
    T, k = map(int, input().split())
    f = [1] * (n + 1)
    s = [i + 1 for i in range(n + 1)]
    for i in range(k, n + 1):
        f[i] = (1 + s[i - k]) % P
        s[i] = (s[i - 1] + f[i]) % P
    for ___ in range(T):
        x, y = map(int, input().split())
        print(((s[y] - s[x - 1]) % P + P) % P)

if __name__ == "__main__":
    main()

思路：考虑以0结尾和以1结尾的序列

python

# 曾孜博  24工学院
t,k=map(int,input().split())
dp=list([0]*2 for _ in range(100001))
p=[0]*(100001)
dp[0][0]=1
dp[0][1]=0
p[0]=1
for i in range(1,100001):
    dp[i][0]=(dp[i-1][0]+dp[i-1][1])%1000000007
    if i>=k:
       dp[i][1]=(dp[i-k][0]+dp[i-k][1])%1000000007
    p[i]=(p[i-1]+dp[i][0]+dp[i][1])%1000000007
for _ in range(t):
    a,b=map(int,input().split())
    print((p[b]-p[a-1])%1000000007)

状态定义：
dp[i][0]: 使用正好 i 朵花，其中最后一朵是红花的所有排列方法数。
dp[i][1]: 使用正好 i 朵花，其中最后 k 朵花是白花的所有排列方法数。
状态转移方程：
如果最后一朵是红花，则前 i−1 朵可以是任意排列： dp[i][0]=dp[i−1][0]+dp[i−1][1]
如果最后 k 朵是白花，则前 i−k 朵可以是任意排列： $d p [i] [1] = d p [i - k] [0] + d p [i - k] [1] (当 i \geq k)$
初始条件：dp[0][0]=1,dp[0][1]=0。当没有花时，只有一种方法，即什么都不选。
前缀和数组：
为了快速计算区间内的方案数，定义数组 p[i]，表示前 i 朵花的方法数总和：
p[i]=p[i−1]+dp[i][0]+dp[i][1]
p[0] = 1
区间求解：
对于每个测试用例的区间 [a,b]，可以通过前缀和快速计算：
$result = p [b] - p [a - 1]$

474D. Flowers ​

474D. Flowers