Codeforces Round #271 (Div. 2) D Flowers【计数dp】
1.5 seconds
256 megabytes
standard input
standard output
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 modulo 1000000007 (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).
思路:
1、设定dp【i】表示长度为i的情况有多少合法放置方式。
dp【i】=dp【i-1】+dp【i-k】;
长度为i-1的时候,直接在其每个合法的放置方式的右边多加一个红色的花也都是合法的情况。
长度为i-k的时候,直接在其每个合法的放置方式的右边多加k个连续白色的花也都是合法的情况。
那么累加即可。
2、那么答案就是sum【bi】-sum【ai】
代码:
#include<bits/stdc++.h>
#define db double
#include<vector>
#define ll long long
#define vec vector<ll>
#define Mt vector<vec>
#define ci(x) scanf("%d",&x)
#define cd(x) scanf("%lf",&x)
#define cl(x) scanf("%lld",&x)
#define pi(x) printf("%d\n",x)
#define pd(x) printf("%f\n",x)
#define pl(x) printf("%lld\n",x)
const int N = 1e5 + ;
const int mod = 1e9 + ;
const int MOD = mod-;
const db eps = 1e-;
const db PI = acos(-1.0);
using namespace std;
ll f[N],sum[N];
int main()
{
int n,k;
ci(n),ci(k);
memset(f,,sizeof(f));
memset(sum,,sizeof(sum));
f[]=;
for(int i=;i<=;i++){
if(i>=k) f[i]=(f[i-]+f[i-k])%mod;
else f[i]=f[i-]%mod;
sum[i]=(sum[i-]+f[i])%mod;
}
for(int i=;i<n;i++){
int l,r;
ci(l),ci(r);
ll ans=(sum[r]-sum[l-]+mod)%mod;
pl(ans);
}
return ;
}
最新文章
- Linq表达式和Lambda表达式用法对比
- jquery——彩色投票进度条
- UVA3026Period(最短循环节)
- 【开源框架】EFW框架中的系统权限与页面子权限详解
- Ubuntu桌面版本和服务器版本之间的区别(转载)
- [SAP ABAP开发技术总结]选择屏幕——PARAMETERS
- show engine innodb status 详解
- 又一编辑神器-百度编辑器-Ueditor
- codevs1127
- Java I/O流操作(二)---缓冲流[转]
- 关于Java泛型的新解
- laravel安装excel功能
- WPF中ContextMenu通过CommandParameter传参
- 【LeetCode】332. Reconstruct Itinerary
- C#基础知识之静态和非静态
- 集合List的排序
- INFO Dispatcher:42 - Unable to find &#39;struts.multipart.saveDir&#39; property setting. Defaulting to javax.servlet.context.tempdir
- 虚幻4引擎角色蓝图Character的Movement组件学习
- GP服务中无Tasks
- Robolectric测试框架使用笔记
热门文章
- <;Openssl下hash函数>;
- Django组件:forms组件(简易版)
- C# Dictionary的遍历
- javascript的常用操作(一)
- orbbec astra ros
- 搭建zabbix服务器监控
- [SVN]TortoiseSVN报“500 Internal Server Error”错误的解决方法
- [:space:]的用法(转)
- javascript HTML静态页面传值的四种方法
- 美国L1签证申请的常见问题解析