1. 一个无穷大的地图，一个人从(0, 0)出发，只能往上、左、右走，一共走k步，走过的格子不能再走，问有多少种不同的走法？只要有一步不同就算做不同。

$k \leq 100$

【题解】打表找规律可知$f_{i} = 2f_{i-1} + f_{i-2}$，那么就套一个高精度啦。复杂度$O(k \times 高精度)$

# include <stdio.h>
# include <algorithm>
# include <stdlib.h>
# include <string.h>
using namespace std;

int n;
struct bign {
	int len, a[120];
}a, b, c;

bign add(bign a, bign b) {
	bign c;memset(c.a, 0, sizeof(c.a));
	c.len=max(a.len, b.len);
	for (int i=1; i<=c.len; ++i) {
		c.a[i]+=a.a[i]+b.a[i];
		if(c.a[i]>=10) {
			c.a[i+1]++;
			c.a[i] %= 10;
		}
	}
	while(c.a[c.len+1] > 0) c.len++;
	return c;
}

bign mul2(bign a) {
	bign c;memset(c.a, 0, sizeof(c.a));
	c.len=a.len;
	for (int i=1; i<=a.len; ++i) {
		c.a[i] += a.a[i]*2;
		if(c.a[i] >= 10) {
			c.a[i+1] = c.a[i]/10;
			c.a[i] %= 10;
		}
	}
	while(c.a[c.len+1] > 0) c.len++;
	return c;
}

inline bign init() {
	bign c; memset(c.a, 0, sizeof(c.a)); c.len=1;
	return c;
}

inline void out(bign a) {
	for (int i=a.len; i>=1; --i) printf("%d", a.a[i]);
	printf("\n");
}

int main() {
	freopen("game.in", "r", stdin);
	freopen("game.out", "w", stdout);

	scanf("%d", &n);
	a=init(), b=init();
	a.a[1]=1, b.a[1]=1;
	for (int i=1; i<=n; ++i) {
		c = add(mul2(b), a);
		a = b;
		b = c;
	}
	out(b);
	
	return 0;
}

2. 给出一个括号描述的树，每个叶子节点有一个bool值，每个非叶子节点有一个操作，奇数层为and，偶数层为or，求出整棵树的表达式值。

$T \leq 100, |S| \leq 30000$

【题解】用栈维护即可。

# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# include <stack>
using namespace std;

char str[33000];
int T;
char opt[300010];
bool num[300010];
int dep[300010];
int optn, numn, depn;

inline int sol() {
	int len = strlen(str) - 1;
	optn = numn = 0;
	int nowdep=0;
	for (int i=0; i<=len; ++i) {
//		printf("i=%d\n", i);
		if(str[i] == '(') {
			opt[++optn] = '(';
			++nowdep;
		} else if(str[i] == ')') {
			--optn;
			bool gg;
			if(nowdep&1) gg=1;
			else gg=0;
			while(numn && dep[numn] == nowdep) {
				if(nowdep&1) gg=gg&num[numn];
				else gg=gg|num[numn];
				--numn;
			}
//			printf("nowdep = %d, gg = %d\n", nowdep, gg);
			num[++numn] = gg;
			--nowdep;
			dep[numn] = nowdep;
		} else if(str[i] == 'T') {
			num[++numn] = 1;
			dep[numn] = nowdep;
		} else if(str[i] == 'F') {
			num[++numn] = 0;
			dep[numn] = nowdep;
		}
	}
	return num[numn];
}

int main() {
	freopen("form.in", "r", stdin);
	freopen("form.out", "w", stdout);
	while(~scanf("%s", str)) {
		++T;
		if(strcmp(str, "()") == 0) break;
		int so = sol();
		printf("%d. %s\n", T, so == 1 ? "true" : "false");
	}
	return 0;
}

3. 问一个$n \times m$的网格，格点为顶点有多少根长度为L的线段。T次询问。

$T \leq 1000, n, m \leq 10^9$

【题解】详情见bzoj1041题解。

# include <stdio.h>
# include <stdlib.h>
# include <math.h>
# include <algorithm>
# include <string.h>
using namespace std;

int n, m, T, L;
const double SQRT2 = sqrt(2);
struct bign {
	int len, a[120];
};

bign add(bign a, bign b) {
	bign c;memset(c.a, 0, sizeof(c.a));
	c.len=max(a.len, b.len);
	for (int i=1; i<=c.len; ++i) {
		c.a[i]+=a.a[i]+b.a[i];
		if(c.a[i]>=10) {
			c.a[i+1]++;
			c.a[i] %= 10;
		}
	}
	while(c.a[c.len+1] > 0) c.len++;
	return c;
}

bign mul(bign a, bign b) {
	bign c;memset(c.a, 0, sizeof(c.a));
	c.len=a.len+b.len-1;
	for (int i=1; i<=a.len; ++i)
		for (int j=1; j<=b.len; ++j) {
			c.a[i+j-1] += a.a[i] * b.a[j];
			if(c.a[i+j-1] >= 10) {
				c.a[i+j] += c.a[i+j-1] / 10;
				c.a[i+j-1] %= 10;
			}
		}
	while(c.a[c.len+1] > 0) ++c.len;
	while(c.a[c.len] >= 10) {
		c.a[c.len+1] = c.a[c.len]/10;
		c.a[c.len]%=10;
		c.len++;
	}
	return c;
}

bign mul2(bign a) {
	bign c;memset(c.a, 0, sizeof(c.a));
	c.len=a.len;
	for (int i=1; i<=a.len; ++i) {
		c.a[i] += a.a[i]*2;
		if(c.a[i] >= 10) {
			c.a[i+1] = c.a[i]/10;
			c.a[i] %= 10;
		}
	}
	while(c.a[c.len+1] > 0) c.len++;
	return c;
}

inline bign init() {
	bign c; memset(c.a, 0, sizeof(c.a)); c.len=1;
	return c;
}

inline bign init(long long num) {
	bign c; memset(c.a, 0, sizeof(c.a)); c.len=0;
	if(num == 0) {
		c.len = 1;
		return c;
	}
	while(num) {
		c.a[++c.len] = num%10;
		num /= 10;
	}
	return c;
}

inline void out(bign a) {
	for (int i=a.len; i>=1; --i) printf("%d", a.a[i]);
	printf(" ");
}

int main() {
	freopen("dist.in", "r", stdin);
	freopen("dist.out", "w", stdout);
	scanf("%d%d%d", &n, &m, &T);
	long long s = (long long)n*n + (long long)m*m;
	if(n>m) swap(n, m);
	while(T--) {
		bign ans=init();
		scanf("%d", &L);
		if((long long)L*L > s) {
			printf("0 ");
			continue;
		}
		if(L < n) 
			ans = add(ans, mul(init(m), init(n-L)));
		if(L < m)
			ans = add(ans, mul(init(n), init(m-L)));
		for (int i=L/SQRT2; i>=1; --i) {
			long long tj = (long long)L*L-(long long)i*i;
			int j = sqrt(tj);
			if(max(i, j) >= m) break;
			if((long long) j*j == tj) {
				// can
				int ni, nj;
				ni = min(i, j), nj = max(i, j);
//				printf("%d %d\n", ni, nj);
				if (ni < n && nj < m)
					ans = add(ans, mul2(mul(init((long long)n-ni), init((long long)m-nj))));
//					out(ans),
//					printf("mul=");
//					out(mul(init((long long)n-ni), init((long long)m-nj))),
//					printf("\n")
				if (ni < m && nj < n) 
					ans = add(ans, mul2(mul(init((long long)m-ni), init((long long)n-nj))));
//					out(ans);	
			}
		}
		out(ans);
	}
	puts("");
	return 0;
}

# include <stdio.h>
# include <stdlib.h>
# include <math.h>
# include <iostream>
# include <algorithm>
# include <string.h>
using namespace std;

int n, m, T;
long long L;
const double SQRT2 = sqrt(2);
long long ans = 0;

/*
A^2 + B^2 = L^2
B^2 = L^2 - A^2 = (L+A) (L-A)
设d = GCD(L+A, L-A)
B^2 = d^2 * (L+A)/d * (L-A)/d
令(L+A)/d=X=x^2, (L-A)/d=Y=y^2
B^2 = d^2 * X * Y = d^2 * x^2 * y^2
X+Y = x^2 + y^2 = 2L/d 
*/

inline long long gcd(long long a, long long b) {
	return b==0 ? a : gcd(b, a%b);
}

inline void get(long long d) { 
//	printf("%d ========\n\n", d);
	long long To = sqrt(d/2);
	long long sqra, sqrb, b;
	long long D = 2*L/d;
	for (long long a=1; a<=To; ++a) {
		sqra = a*a;
		sqrb = d - sqra;
		b = sqrt(sqrb);
		//printf("%d %d %d\n", a, b, d); 
		//cout << sqra << ' ' << sqrb << "fuck" << endl; 
		if(b*b == sqrb && gcd(sqra, sqrb) == 1 && sqra != sqrb) {
			long long A = a*b*D, B = sqrt(L*L - A*A);
			if(A<n && B<m)  { 
				//printf("a=%I64d, b=%I64d, A=%I64d, B=%I64d, d=%I64d, D=%I64d\n", a, b, A, B, d, D); 
				ans = ans + 2LL*((long long)n-A)*((long long)m-B); 
				//printf("%lld\n", ans);
			}
		}
	}
}
		
int main() {
	freopen("dist.in", "r", stdin);
	freopen("dist.out", "w", stdout);
	scanf("%d%d%d", &n, &m, &T);
	if(n>m) swap(n, m);
	for (int Test = 1; Test <= T; ++Test) { 
		ans = 0;
		scanf("%I64d", &L);
		if(L < n) ans += (long long)m * (n-L);
		if(L < m) ans += (long long)n * (m-L);
		long long To = sqrt(2*L); 
		for (long long d=1; d<=To; ++d) {
			if(2*L%d != 0) continue;
//			printf("%d %d\n", d, 2*L/d); 
			get(d);
			if(d != 2LL*L/d) get(2LL*L/d);
		}
		if(Test!=T) printf("%I64d ", ans); 
		else printf("%I64d", ans); 
	}
	return 0;
}