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[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;
}

Leave a Reply

Your email address will not be published.

− 1 = 4