Andrew Stankevich’s Contest #8解题报告 » ZOJ2671

ZOJ2671
ZOJ2671.cpp


#include <cstdio>

// |a b|
// |c d|

struct LT {
	int a, b, c, d;
};

const int MAXN = 32768;
const LT e = {1, 0, 0, 1};

int R;
LT a[MAXN << 1];

#define L(i) ((i) << 1)
#define R(i) (L(i) ^ 1)

inline void product(const LT& lhs, const LT& rhs, LT& ret) {
	ret.a = (lhs.a * rhs.a + lhs.b * rhs.c) % R;
	ret.b = (lhs.a * rhs.b + lhs.b * rhs.d) % R;
	ret.c = (lhs.c * rhs.a + lhs.d * rhs.c) % R;
	ret.d = (lhs.c * rhs.b + lhs.d * rhs.d) % R;
}

LT gao(int p, int pl, int pr, int l, int r) {
	if (l == pl && r == pr) {
		return a[p];
	} else {
		int pm = (pl + pr) >> 1;
		if (r <= pm) {
			return gao(L(p), pl, pm, l, r);
		} else if (pm <= l) {
			return gao(R(p), pm, pr, l, r);
		} else {
			LT ret;
			product(gao(L(p), pl, pm, l, pm), gao(R(p), pm, pr, pm, r), ret);
			return ret;
		}
	}
}

int main() {
	int n, m, s, l, r;
	bool blank = false;
	LT ans;

	while (scanf("%d%d%d", &R, &n, &m) != EOF) {
		s = 1;
		while (s < n) {
			s <<= 1;
		}
		for (int i = 0; i < n; ++i) {
			scanf("%d%d%d%d", &a[s + i].a, &a[s + i].b, &a[s + i].c, &a[s + i].d);
		}
		for (int i = s - 1; i >= 1; --i) {
			product(a[L(i)], a[R(i)], a[i]);
		}
		for (int i = 0; i < m; ++i) {
			scanf("%d%d", &l, &r);
			ans = gao(1, 0, s, l - 1, r);
			if (blank) {
				putchar('\n');
			} else {
				blank = true;
			}
			printf("%d %d\n%d %d\n", ans.a, ans.b, ans.c, ans.d);
		}
	}

	return 0;
}
//Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name
//1974083 	2009-08-19 00:47:16 	Accepted 	2671 	C++ 	670 	1200 	watashi@Zodiac
/*
Submit Time  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name
2009-08-19 00:47:16 	C++ 	670 	1200 	watashi@Zodiac
2009-02-07 15:47:31 	C++ 	720 	3928 	HyperHexagon
2009-04-03 18:06:50 	C++ 	740 	2060 	asmn@Runic
2009-07-20 15:19:14 	C++ 	880 	4160 	pkkj
2009-03-30 22:32:58 	C++ 	900 	2060 	LZOI_LCLL
2009-08-02 14:50:15 	C++ 	920 	4396 	joey2005
2009-02-04 22:56:50 	C++ 	1030 	8368 	davidsun
2009-04-08 13:17:44 	C++ 	1530 	7684 	macs
2006-03-11 19:50:05 	C++ 	1710 	2440 	foolman
2006-03-17 19:57:53 	FPC 	1770 	4332 	SpeedStar
*/
One Response to “ZOJ2671”
  1. wuyongxing says:

    good

  2.  
Leave a Reply