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 modulo1000000007 (109 + 7).
Input contains several test cases.
The first line contains two integers t and k (1 ≤ t, k ≤ 105), where t represents the number of test cases.
The next t lines contain two integers ai and bi (1 ≤ ai ≤ bi ≤ 105), describing the i-th test.
Print t lines to the standard output. The i-th line should contain the number of ways in which Marmot can eat between ai and bi flowers at dinner modulo 1000000007 (109 + 7).
3 2 1 3 2 3 4 4
6 5 5
- 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).
题意:
给出 t 和 k,代表有 t 组询问。k 代表一次只能吃 k 朵 W 花,后给出 t 组的 a - b 区间。问吃这段区间内的长度序列满足条件的方法数。
思路:
DP。dp [ i ] = dp [ i - k ] + dp [ i - 1] 代表一次要么连续吃 k 朵 W 花,要么一次吃 1 朵 R 花。记得最后答案中的减法后要 + MOD 再 % MOD。不然会出错。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const ll MOD = 1000000007; const int MAX = 100005; ll dp[MAX]; ll sum[MAX]; ll a[MAX], b[MAX]; int main() { int t, k; scanf("%d%d", &t, &k); ll Max = 0; for (int i = 1; i <= t; ++i) { scanf("%I64d%I64d", &a[i], &b[i]); Max = max(Max, b[i]); } for (int i = 0; i < k; ++i) { dp[i] = 1; sum[i] = sum[i - 1] + dp[i]; } for (int i = k; i <= Max; ++i) { dp[i] = (dp[i - k] + dp[i - 1]) % MOD; sum[i] = (dp[i] % MOD + sum[i - 1] % MOD) % MOD; } for (int i = 1; i <= t; ++i) { printf("%I64d\n", (sum[b[i]] - sum[a[i] - 1] + MOD) % MOD); } return 0; }
相关推荐
训练集和验证集各包含1020张图片,此外还包括额外6149的额外测试集图像。更加详细的数据集介绍可以参考:https://www.robots.ox.ac.uk/~vgg/data/flowers/102/
Wordpress Vector Flowers模板
Ox-Flowers17 包含17种不同类型的花,每类包含80张RGB图
17flowers图片数据集,共17种花的类别,每种花有80张jpg图片 按花的类别整理17个子文件夹
17flowers.tgz,是从 tflearn/example里下载保存的。Oxford 17类鲜花数据集。
Oxford 102 Flowers Dataset 是一个花卉集合数据集,主要用于图像分类,它分为 102 个类别共计 102 种花,其中每个类别包含 40 到 258 张图像。 该数据集由牛津大学工程科学系于 2008 年发布,相关论文有...
Flowers Recognition(花卉识别数据集).zip
tensorflow tf_flowers数据集, win路径C:\Users\yourname\tensorflow_datasets\tf_flowers\3.0.1\*, linux路径:/root/tensorflow_datasets/tf_flowers/3.0.1/*
Oxford 102 Flowers Dataset 是一个花卉集合数据集,主要用于图像分类,它分为 102 个类别共计 102 种花,其中每个类别包含 40 到 258 张图像。 该数据集由牛津大学工程科学系于 2008 年发布,相关论文有...
Wallpaper_Engine Hidden In Flowers
17flowers_data图片集压缩包(未划分);统一像素及划分训练集样本集代码在笔者 机器学习实战笔记5——线性判别分析 里有提供
OxfordFlowers_102_102flowers.tgz
总计1360张分类好的花的图像,图像的大小有(500,500)(500,600)不等,已经分类为17类好,标签可以自己自行获取,该图像出处忘了,仅供大家学习使用,配合代码练习,加深对机器学习的理解。
处理好的flowers17数据集,包含训练集、验证集和测试集,和相应的数据集分类代码。
该dataset中共有17种类型的花,已经分好类别,2个文件夹分别为训练集和测试集,每一类别的花在一个单独的文件夹中
120flowers的40个类,由于全部数据量太大,无法直接上传,所以分开上传。已经将其余的62类上传,数据全部处理好,可直接使用
Pku acm 第1157题 LITTLE SHOP OF FLOWERS c代码,有详细的注释,动态规划
FLOWERS5.WMF
采用JavaScript添加动态效果,不停变换页面
该网页资源由html5和javascript构建,实现了花瓣飞舞的效果,想学习js动画或者借用现成实现的可以参考该资源。