codeforce474D

codeforce474D_组合

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

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

思路：dp[i] = dp[i - 1] + dp[i - k]

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 #define LL long long
 6 using namespace std;
 7 
 8 const int N = 1e5;
 9 const int mod = 1e9 + 7;
10 LL num[N + 10], abc[N + 10];
11 int t, k, a, b;
12 void find()
13 {
14     for(int i = 1; i < k; i++)
15         num[i] = 1;
16     num[0] = 0;
17     num[k] = 2;
18     for(int i = k + 1; i <= N; i++)
19         num[i] = (num[i - 1] + num[i - k]) % mod;//num[i]表示长度为i时的种类有多少
20     abc[0] = 0;
21     for(int i = 1; i <= N; i++)
22         abc[i] = (abc[i - 1] + num[i]) % mod;//长度为[1, i]时的种数
23 }
24 int main()
25 {
26     scanf("%d %d", &t, &k);
27     find();
28     while(t--)
29     {
30         scanf("%d %d", &a, &b);
31         LL res = (abc[b] - abc[a - 1]) % mod;
32         if(res < 0)
33             res = res + mod;
34         printf("%I64d
", res);
35     }
36     return 0;
37 }