# ZOJ 3725 Painting Storages

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 = 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;
}
```