某岛

… : "…アッカリ～ン . .. . " .. .
March 24, 2011

ZOJ 3256. Tour in the Castle

Brief description :

起点终点固定的“一条路径”问题。
（.. H <= 10^9，W <= 7 ..）

Analyse :

… 

#include 
#include 
#include 
#include 
using namespace std;   
const int ww = 7, _W = 16, ll = 127;
const int _P = 7777777; 

map H; int ST;
int L[ll], h, w, n, up, l;
int i, s, ans;


struct matrix{
	int d[ll][ll];
	matrix(){
		memset(d, 0, sizeof(d));
	}
} A, C;

matrix operator *(const matrix& a, const matrix& b){
	matrix c;
	for (int i=1;i> 1);
    x = (x & 0x00003333) + ((x & 0x0000cccc) >> 2);
    x = (x & 0x00000f0f) + ((x & 0x0000f0f0) >> 4);
    x = (x & 0x000000ff) + ((x & 0x0000ff00) >> 8);
    return x;
}

void eatLeft(int i){
	int An = 0;
	for (i--;;i--){
		if (!_Pi) continue;
		if (_Ti) An++;
		else {if (An==0){_Ci; return;} An--;}
	}
}
void eatRight(int i){
	int An = 0;
	for (i++;;i++){
		if (!_Pi) continue;
		if (!_Ti) An++;
		else {if (An==0){_Ci; return;} An--;}
	}
}



void dfs(int l){
	if (l == w){
		A.d[i][H[s]] = 1;
	}
	else {
		int r = l + 1;
		int c = s;
		
		if (_Pl){
			// 0: Stable ..
			dfs(r);
			
			if (_Tl){  
				// 2: Move_Right with ')' . ..
				while (r < w && !_Pr){ 
					_Sl; _Cl; _Sr; _Cr; dfs(++r); s = c;
				}
				
				// 4: Merge with '))'
				if (r < w){
					if (_Tr){
						eatLeft(l); _Sl; _Cl; _Sr; _Cr; dfs(r+1); s = c;
					}
					// 4: Merge with ')('
					else {
						_Sl; _Cl; _Sr; dfs(r+1); s = c;
					}
				}
			}
			else {
				// 2: Move_Right with '(' . ..
				while (r < w && !_Pr){
					_Sl; _Sr; dfs(++r); s = c;
				}
				
				// 4: Merge with '(('
				if (r < w){
					if (!_Tr){
						eatRight(r); _Sl; _Sr; dfs(r+1); s = c;
					}
					// 4 Merge with '()'
					else {
						//!..#>..#>.f                         
						if (r + 1 == w &&  countBits(s)==2){
							A.d[i][0] = 1;
						}
					}
				}
			}
			
		}
		else {
			// 3: Bown a pair of new plug . ...
			while (r < w && !_Pr){
				_Sl; _Sr; _Cr; dfs(++r); s = c;
			}
			
			// 1 Move_Left
			if (r < w){
				if (_Tr) {_Sl; _Cl; _Sr; _Cr; dfs(r+1); s = c;}
				else {_Sl; _Sr; dfs(r+1); s = c;}
			}
		}
	}
}


void scan(int i, int ln, int rn){
	while (!_Pi) i++;
	
	if (i==w) {
		H[s ^ up] = l;
		L[l++] = s ^ up;
	}
	else {
		if (ln < n) scan(i+1, ln+1, rn);
		if (rn < ln) {_Ci; scan(i+1, ln, rn+1); _Ci;}
	}
}

void init(){
    memset(A.d, 0, sizeof(A.d));
	l = 0, up = 1 << w, H.clear();
	
	for (i = 0; i < up; i ++){
		n = countBits(i);
		if ((n&1)==0){s = i | up, n >>= 1, scan(0, 0, 0);}
	}
	
	ST =  H[1 | 1 << (w - 1) | 1 << (_W + w - 1)]; //初始匹配
	for (i = 1; i < l; i ++)
		s = L[i], dfs(0);	
}

void solve(){
	C = pow(A, h);
	ans = C.d[ST][0];
}

int main(){        
    //freopen("in.txt", "r", stdin);
	while (scanf("%d%d", &w, &h)==2){
		init(); solve();
		if (ans == 0) cout << "Impossible" << endl;
		else cout << ans << endl;
	}
}

// 1, 1, 2, 4, 9, 21, 51, 127, 323, 835, 2188, 5798, 15511, 41835, 113634, 155126,


Further discussion

母题里写了两种方法，这题建矩阵的时候明显采取 DFS 逐行递推更清楚。
。。（ TLE 不能自已 。。。直到 hpfdf 神犇的强势 Debug 下，知道矩阵乘法的时候，要累积到平方再取模。。。。。。掩面。 。＝ =。。）

External link :

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3540

Posted by xiaodao
Category: 日常
Tags:

« | »

  • Archives

    open all | close all