ACM解题总结——HihoCoder1048

/****************************************************/
/* File        : HihoCoder1048                      */
/* Author      : Zhang Yufei                        */
/* Date        : 2016-05-03                         */
/* Description : HihoCoder ACM program. (submit:g++)*/
/****************************************************/

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

#define MOD 1000000007

// Record the input.
int N, M;

// Define the matrix for dp.
int ***dp;

/*
 * This function gets the bit from the state according to the given position.
 * Parameters:
 *		@state: The state value.
 *		@position: The position to get.
 *		@tag: If tag = 0, get bit from p1, p2 ... pm; if tag = 1, get bit from
 *			q1, q2 ... qm.
 * Returns:
 *		The result bit;
 */
int get_bit(int state, int position, int tag);

/*
 * This function puts a piece of cake in the given postion.
 * Parameters:
 *		@state: The original state.
 *		@y: The position to put (only y coordinate value).
 *		@tag: If tag = 1, put the cake in horizontical way, or in vertical way.
 * Returns:
 *		The new status value after putting.
 */
int put_cake(int state, int y, int tag);

int main (void) {

	scanf ("%d %d", &N, &M);

	int state_cnt = pow (2, M * 2);
		
	dp = (int***) malloc (sizeof (int**) * N);
	
	for(int i = 0; i < N; i++) {
		dp[i] = (int**) malloc (sizeof (int*) * M);
		for(int j = 0; j < M; j++) {
			dp[i][j] = (int*) malloc (sizeof (int) * state_cnt);
		}
	}
	
	for(int i = N - 1; i >= 0; i--) {
		for(int j = M - 1; j >= 0; j--) {
			for(int k = state_cnt - 1; k >= 0; k--) {
				int pj = get_bit(k, j, 0);
				if(pj == 1) {
					if(j < M - 1) {
						dp[i][j][k] = dp[i][j + 1][k];
					} else if(j == M - 1){
						if(i == N - 1) {
							dp[i][j][k] = 1;
						} else {
							dp[i][j][k] = dp[i + 1][0][(k << M) % state_cnt];
						}
					}
				} else {
					dp[i][j][k] = 0;
					
					if(j < M - 1) {
						int pj1 = get_bit(k, j + 1, 0);
						
						if(pj1 == 0) {
							int state = put_cake(k, j, 0);
							dp[i][j][k] += dp[i][j][state]; 
						}
					}
					
					if(i < N - 1) {
						int qj = get_bit(k, j, 1);
						if(qj == 0) {
							int state = put_cake(k, j, 1);
							dp[i][j][k] += dp[i][j][state];
							dp[i][j][k] %= MOD;
						}
					}
				}
			}		
		}
	}
	
	printf("%d\n", dp[0][0][0]);
	
	return 0;
} 

/*
 * This function gets the bit from the state according to the given position.
 * Parameters:
 *		@state: The state value.
 *		@position: The position to get.
 *		@tag: If tag = 0, get bit from p1, p2 ... pm; if tag = 1, get bit from
 *			q1, q2 ... qm.
 * Returns:
 *		The result bit;
 */
int get_bit(int state, int position, int tag) {
	if(tag == 0) {
		state = state >> M;
	}
	
	int r = 0;
	for(int i = 0; i < M - position; i++) {
		r = state % 2;
		state /= 2; 
	}	
	
	return r;
}

/*
 * This function puts a piece of cake in the given postion.
 * Parameters:
 *		@state: The original state.
 *		@y: The position to put (only y coordinate value).
 *		@tag: If tag = 1, put the cake in horizontical way, or in vertical way.
 * Returns:
 *		The new status value after putting.
 */
int put_cake(int state, int y, int tag) {
	int r = 1;
	for(int i = 0; i < M - y - 1; i++) {
		r = r << 1;
	}
	
	if(tag == 0) {
		r = r << M;
		state = state | r;
		r = r >> 1;
		state = state | r;
	} else {
		state = state | r;
		r = r << M;
		state = state | r; 
	}
	
	return state;
}