This problem can be found here

ZOJ Problem Set - 3725

Painting Storages

Time Limit: 2 Seconds

Memory Limit: 65536 KB

```
```There is a straight highway with N storages alongside it labeled by 1,2,3,...,N. Bob asks you to paint all storages with two colors: red and blue. Each storage will be painted with exactly one color.

Bob has a requirement: there are at least M continuous storages (e.g. "2,3,4" are 3 continuous storages) to be painted with red. How many ways can you paint all storages under Bob's requirement?

Input

There are multiple test cases.

Each test case consists a single line with two integers: N and M (0<N, M<=100,000).

Process to the end of input.

Output

One line for each case. Output the number of ways module 1000000007.

Sample Input

4 3

Sample Output

`3`

It is not hard to find that this is another dynamic programming problem. An O(n^2) solution is not acceptable, it should be done better.

Notation: we use f[i] to keep the number of ways for i storages.

(1) if m continuous red storages are found before i, we definitely have `f[i] = f[i-1] * 2`

(2) if the (i-1)th, (i-2)th … (i-m+1)th storage is red and the (i-m)th one is blue, then we can make the ith one red, regardless of the combination of the first i-m-1 storages. `f[i] += 2^(i-m-1)`

. But in this situation, we must make sure that there are no m continuous red ones in the first (i-m-1) storages, otherwise it is duplicate as case(1). `f[i] -= f[i-m-1]`

.

So finally the function is:

`f[i] = (f[i-1]*2) + 2^(i-m-1) - f[i-m-1]`

Be careful about the boundary cases and we will reach the solution.

//ZOJ 3725 //LANG C++ #include <iostream> #define MOD 1000000007 #define MAX 100001 using namespace std; //Using long long makes life much easier long long p[MAX]; //p[i] = (2^i)%MOD long long f[MAX]; int main() { p[0] = 1; for(int i=1; i<MAX; i++) p[i] = (p[i-1]*2)%MOD; int n, m; while((cin>>n>>m)) { //Boundary cases for(int i=0; i<m; i++) f[i] = 0; f[m] = 1; f[m+1] = 3; //DP for(int i=m+2; i<=n; i++) { f[i] = ((f[i-1]*2) + p[i-m-1] - f[i-m-1])%MOD; if(f[i]<0) f[i]+=MOD; } cout<<f[n]<<endl; } return 0; }