[TIOJ] 1117. Walsh code

題目連結:http://tioj.infor.org/problems/1117

---

學測念不完，可是又要北市賽了QQ只好把市賽題刷一刷，希望至少市賽不要出事
最近真的好笨，只會一些straightforward的題目，這題還是被雷的才出來的。
總之核心問題就是我們不能一次做太多事、要一步一步來，畢竟他每次要輸出的字串也沒多長。
那所以我們就每次要知道第n個矩陣的第i,j元素，而這可以直接根據定義直接看他在哪一塊，並且遞迴下去就會得知答案了。

#include <bits/stdc++.h>
using namespace std;

bool go(int,int,int);

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	for(int n, i, a, b;cin >> n >> i >> a >> b;){
		for(int j=a;j<=b;j++)
			cout << (go(n, i-1, j-1)?"+1":"-1") << " \n"[j==b];
	}
	return 0;
}

bool go(int n, int x, int y) {
	if(n == 0) return 0;
	int tl = (1<<(n-1));
	if(x >= tl and y >= tl) return go(n-1, x-tl, y-tl)^1;
	if(x >= tl) x -= tl;
	if(y >= tl) y -= tl;
	return go(n-1, x, y);
}