CodeForces 474.D Flowers
2024-08-26 06:32:50
题意:
有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]
然后预处理一下前缀和。
代码中注意取模。
#include <cstdio>
const int maxn = + ;
const int MOD = + ;
int d[maxn]; int main()
{
int t, k, i;
scanf("%d%d", &t, &k); d[] = ;
for(i = ; i < k; ++i) d[i] = ;
for(; i < maxn; ++i) d[i] = (d[i-] + d[i - k]) % MOD; for(i = ; i < maxn; ++i) d[i] = (d[i] + d[i-]) % MOD;
for(i = ; i < t; ++i)
{
int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", (d[b] - d[a-] + MOD) % MOD);
} return ;
}
代码君
最新文章
- OGNL的使用
- .NET导入Excel到SQL数据库
- Dapper的基本使用
- EF框架中加子类后出现列名 &#39;Discriminator&#39; 无效问题
- SQL2005删除复制数据库的发布与订阅的方法(转载)
- 《MySQL必知必会》笔记 事务、安全及性能等
- redhat的启动方式和执行次序
- about backbone
- PARTITION BY 和 group by
- c++读写MySQL
- php实现栈操作(不用push pop 库函数)
- Jmeter登录后Session自动共享与多线程组并行
- [Android Pro] 完美解决 No toolchains found in the NDK toolchains folder for ABI with prefix: mips64el-linux-android
- html中header,footer分别固定在顶部和底部
- 06-02 Java值传递、数据加密
- 《利用Python进行数据分析》笔记---第5章pandas入门
- JDBC 实例--JDBC通过工具类DBUtil连接到数据库,让我们不再恐惧操作数据库
- Maven的pom文件配置
- E: 无法获得锁 /var/cache/apt/archives/lock - open (11 资源临时不可用)
- 使用Jenkins集成和自动化打包资料