题目链接:http://codeforces.com/problemset/problem/474/D

用RW组成字符串,要求w的个数要k个连续出现,R任意,问字符串长度为[a, b]时,字符串的种类有多少。

递推,dp[i]表示长度为i的种类有多少。当i < k的时候 dp[i] = 1 , 当i == k的时候 dp[i] = 2 ,  否则 dp[i] = dp[i - 1] + dp[i - k] 。

 #include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + ;
typedef __int64 LL;
LL mod = 1e9 + ;
LL dp[MAXN] , ans[MAXN];
int main()
{
int n , k , a , b;
scanf("%d %d" , &n , &k);
dp[] = ;
ans[] = ;
for(int i = ; i <= 1e5 ; ++i) {
if(i >= k)
dp[i] = (dp[i - k] + dp[i - ]) % mod;
else
dp[i] = ;
ans[i] = (ans[i - ] + dp[i]) % mod;
}
while(n--) {
scanf("%d %d" , &a , &b);
printf("%lld\n" , (ans[b] - ans[a - ] + mod) % mod);
}
return ;
}

最新文章

  1. java.lang.IllegalStateException: Not allowed to create transaction on shared EntityManager - use Spring transactions or EJB CMT instead
  2. JS编码解码
  3. Linux练习
  4. &lt;&lt;卸甲笔记&gt;&gt;-基础语法对比
  5. 简单验证码实现(Ajax)
  6. 在运行程序时报错:&quot;如果在 Code First 模式下使用,则使用 T4 模板为 Database First 和 Model First 开发生成的代码可能无法 正常运行。若要继续使用 Database First 或 Model First,请确保在执行应用程序的 config 文件中指 定 Entity Framework 连接字符串。若要将这些从 Database First 或 Mod
  7. 微信JS SDK Demo 官方案例
  8. 【转载】ITU-RBT.656视频标准接口
  9. ThinkPHP技巧
  10. UML时序图
  11. POJ 2828 Buy Tickets (线段树 or 树状数组+二分)
  12. C++静态变量对象的建立和删除,兼论MFC开始运行的起点(全局对象)
  13. 深入理解shared pool共享池之library cache系列二
  14. Java设计模式模式观测(Observer Pattern)
  15. SpringMVC中404错误解决方法总结
  16. ABP框架 - 规约
  17. QT 启动shell脚本
  18. P1913 L国的战斗之伞兵(广搜BFS)
  19. Shuffle 洗牌 [AHOI 2005]
  20. 20145320《网络对抗》注入Shellcode并执行

热门文章

  1. HDU3709 Balanced Number (数位dp)
  2. POJ 2752 (KMP 所有可能长度的前缀后缀) Seek the Name, Seek the Fame
  3. Only one instance of a ScriptManager can be added to the page.
  4. 试图从数据库 ‘UFData_001_2003&#39; 中提取的逻辑页 (1:10720) 属于对象 &#39;0&#39;,而非对象 &#39;syscolumns&#39;
  5. Mac下配置PHP+Apache+phpMyAdmin+MySql远程链接
  6. Java 单元测试(Junit)
  7. Java之UncaughtExceptionHandler
  8. 1048 图的宽度优先遍历序列 c语言
  9. IOS 本地通知UILocalNotification
  10. 【C++对象模型】函数返回C++对象的问题