fzu 1911 Construct a Matrix(矩阵快速幂+规律）

题目链接：fzu 1911 Construct a Matrix

题目大意：给出n和m，f[i]为斐波那契数列，s[i]为斐波那契数列前i项的和。r = s[n] % m。构造一个r * r的矩阵，只能使用-1、0、1。使得矩阵的每行每列的和都不相同，输出方案，不行的话输出No。

解题思路：求r的话用矩阵快速幂求，每次模掉m，

{ {1， 1， 0}， {1， 0， 0}， {1， 1， 1} } * { f[i], f[i -1], s[i] } = { f[i + 1], f[i], s[i + 1] }.

然后求出r后，若r是奇数或0，则矩阵不存在；r为偶数时，只要按照规律建立矩阵就可以了。

#include <stdio.h>

#include <string.h>

const int M = 10;

const int N = 205;

int n, m, r;

struct Mul {

	int s[M][M];

	Mul() {	memset(s, 0, sizeof(s));	}

	Mul operator * (const Mul& c) {

		Mul ans;

		for (int i = 0; i < 3; i++) {

			for (int j = 0; j < 3; j++) {

				ans.s[i][j] = 0;

				for (int k = 0; k < 3; k++)

					ans.s[i][j] = (ans.s[i][j] + s[i][k] * c.s[k][j] ) % m;

			}

		}

		return ans;

	}

	void put() {

		for (int i = 0; i < 3; i++) {

			for (int j = 0; j < 3; j++)

				printf("%d ", s[i][j]);

			printf("\n");

		}

	}

};

Mul MulPow(Mul a, int t) {

	if (t == 1) return a;

	Mul x = MulPow(a, t / 2);

	x = x * x;

	if (t % 2) x = x * a;

	return x;

}

void init() {

	if (n > 2) {

		Mul a;

		a.s[0][0] = a.s[0][1] = a.s[1][0] = a.s[2][0] = a.s[2][1] = a.s[2][2] = 1;

		Mul ans = MulPow(a, n - 2);

		r = (ans.s[2][0] + ans.s[2][1] + ans.s[2][2] * 2) % m;

	} else if (n == 2) {

		r = 2 % m;

	} else if (n == 1) {

		r = 1;

	}

}

void solve() {

	if (r == 0 || r % 2)

		printf("No\n");

	else {

		int v[N][N];

		memset(v, -1, sizeof(v));

		printf("Yes\n");

		for (int i = 1; i <= r; i++) {

			int tmp;

			if (i % 2) {

				tmp = (r + i + 1) / 2;

				v[tmp][i] = 0;

			} else

				tmp = (r - i) / 2;

			for (int j = tmp + 1; j <= r; j++)

				v[j][i] = 1;

		}

		for (int i = 1; i <= r; i++) {

			for (int j = 1; j < r; j++)

				printf("%d ", v[i][j]);

			printf("%d\n", v[i][r]);

		}

	}

}

int main () {

	int cas;

	scanf("%d", &cas);

	for (int i = 1; i <= cas; i++) {

		scanf("%d%d", &n, &m);

		printf("Case %d: ", i);

		init();

		solve();

	}

	return 0;

}

巴特西

fzu 1911 Construct a Matrix(矩阵快速幂+规律）

最新文章

热门文章