花束（flwr）

题目描述

Y 同学要制作若干长度不同的花束。每一束可以由若干朵红花和白花组成，但白花必须按连续的 $k$ 朵作为一组加入，红花可以单朵加入。

设 $f_x$ 表示制作长度恰好为 $x$ 的花束的方案数。现在有 $q$ 次询问，每次给出 $l,r$ ，请你求出

\sum_{x=l}^{r} f_x

对 $10^9+7$ 取模后的结果。

第一行包含两个整数 $q,k$ 。

接下来 $q$ 行，每行包含两个整数 $l,r$ 。

对于每次询问，输出一行一个整数，表示答案。

6
18
5

对于 $100\%$ 的数据，保证 $1 \le q \le 2\times 10^5$ ， $1 \le k \le 2\times 10^5$ ， $1 \le l \le r \le 2\times 10^5$ 。

测试点编号	分值	$q \le$	$r \le$	特殊性质
$1 \sim 2$	$10$	$20$	$30$	无
$3 \sim 5$	$15$	$5000$	$2\times 10^5$	特殊性质 A
$6 \sim 8$	$15$	$2\times 10^5$	$30$	特殊性质 B
$9 \sim 12$	$20$		$2\times 10^5$	无
$13 \sim 16$
$17 \sim 20$

难度 7

通过率 33.3%

ID 499

类型传统题

Time Limit 1000ms

Memory Limit 256MiB

上传者