首页 > 代码库 > CodeForces 474.D Flowers
CodeForces 474.D Flowers
题意：
有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 <cstdio> 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 }
CodeForces 474.D Flowers
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。