博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
CodeForces 474.D Flowers
阅读量:5277 次
发布时间:2019-06-14

本文共 846 字,大约阅读时间需要 2 分钟。

题意:

有n朵花排成一排,小明要么吃掉连续的k朵白花,或者可以吃单个的红花。

给出一个n的区间[a, b],输出总吃花的方法数模 109+7 的值。

分析:

设d(i)表示吃i朵花的方案数。

则有如下递推关系:

d[i] = d[i-1] + d[i-k], (i ≥ k, d[0] = 1)

我们在计数i+1的情况时,可以分为如下两种情况:

  • 最后一朵是红花,方案数为d[i]
  • 最后k朵是白花,方案数为d[i-k]

然后预处理一下前缀和。

代码中注意取模。

1 #include 
2 const int maxn = 100000 + 10; 3 const int MOD = 1000000000 + 7; 4 int d[maxn]; 5 6 int main() 7 { 8 int t, k, i; 9 scanf("%d%d", &t, &k);10 11 d[0] = 1;12 for(i = 1; i < k; ++i) d[i] = 1;13 for(; i < maxn; ++i) d[i] = (d[i-1] + d[i - k]) % MOD;14 15 for(i = 1; i < maxn; ++i) d[i] = (d[i] + d[i-1]) % MOD;16 for(i = 0; i < t; ++i)17 {18 int a, b;19 scanf("%d%d", &a, &b);20 printf("%d\n", (d[b] - d[a-1] + MOD) % MOD);21 }22 23 return 0;24 }
代码君

 

转载于:https://www.cnblogs.com/AOQNRMGYXLMV/p/4104016.html

你可能感兴趣的文章
TYVJ.1864.[Poetize I]守卫者的挑战(概率DP)
查看>>
0925 韩顺平java视频
查看>>
iOS-程序启动原理和UIApplication
查看>>
mysql 8.0 zip包安装
查看>>
awk 统计
查看>>
模板设计模式的应用
查看>>
实训第五天
查看>>
平台维护流程
查看>>
2012暑期川西旅游之总结
查看>>
12010 解密QQ号(队列)
查看>>
2014年辛星完全解读Javascript第一节
查看>>
装配SpringBean(一)--依赖注入
查看>>
java选择文件时提供图像缩略图[转]
查看>>
方维分享系统二次开发, 给评论、主题、回复、活动 加审核的功能
查看>>
Matlab parfor-loop并行运算
查看>>
string与stringbuilder的区别
查看>>
2012-01-12 16:01 hibernate注解以及简单实例
查看>>
iOS8统一的系统提示控件——UIAlertController
查看>>
PAT甲级——1101 Quick Sort (快速排序)
查看>>
python创建进程的两种方式
查看>>