Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

贴一个一般般的代码

Posted by a280920481 at 2018-11-29 16:08:20
#include <iostream>
using namespace std;

struct Matrix//矩阵
{
	int e[30][30];//矩阵的元素
};


Matrix powF[32][2][2];//存储初始矩阵的 1 到 31 次幂 (powF[0] 均为零矩阵)

void mult(Matrix * x, Matrix * y, Matrix * res, int & n, int & m);//(n 阶矩阵对 m 取模) 把 x * y 输出至 res

void add(Matrix * x, Matrix * y, Matrix * res, int & n, int & m);//(n 阶矩阵对 m 取模) 把 x + y 输出至 res

void cpy(Matrix * tar, Matrix * x, int & n);//(n 阶矩阵) 把 x 拷贝至 tar

void output(Matrix * x, int & n);//打印 n 阶矩阵 x

int main()
{
	int n, k, m, t;
	Matrix sumA, tA, tF[2][2], ansF[2][2];

	cin >> n >> k >> m;

	k++;//需要计算矩阵的 k + 1 次幂


	for (int k1 = 0; k1 < 2; k1++)
	{
		for (int k2 = 0; k2 < 2; k2++)
		{
			cpy(&ansF[k1][k2], &powF[0][0][0], n);
		}
	}

	for (int k1 = 0; k1 < n; k1++)
	{
		for (int k2 = 0; k2 < n; k2++)
		{
			cin >> t;
			powF[1][0][0].e[k1][k2] = t % m;
		}
		powF[1][1][0].e[k1][k1] = 1;
		powF[1][1][1].e[k1][k1] = 1;

		ansF[0][0].e[k1][k1] = 1;
		ansF[1][1].e[k1][k1] = 1;

	}

	//计算初始矩阵的 2 到 31 次幂
	for (int i = 2; i < 32; i++)
	{
		for (int k1 = 0; k1 < 2; k1++)
		{
			for (int k2 = 0; k2 < 2; k2++)
			{
				cpy(&sumA, &powF[0][0][0], n);
				for (int j = 0; j < 2; j++)
				{
					mult(&powF[i - 1][k1][j], &powF[i - 1][j][k2], &tA, n, m);
					add(&sumA, &tA, &sumA, n, m);
				}
				cpy(&tF[k1][k2], &sumA, n);
			}
		}
		for (int k1 = 0; k1 < 2; k1++)
		{
			for (int k2 = 0; k2 < 2; k2++)
			{
				cpy(&powF[i][k1][k2], &tF[k1][k2], n);
			}
		}
	}

	int p = 0;

	while (k)
	{
		p++;
		if (k & true)
		{
			for (int k1 = 0; k1 < 2; k1++)
			{
				for (int k2 = 0; k2 < 2; k2++)
				{
					cpy(&sumA, &powF[0][0][0], n);
					for (int j = 0; j < 2; j++)
					{
						mult(&powF[p][k1][j], &ansF[j][k2], &tA, n, m);
						add(&sumA, &tA, &sumA, n, m);
					}
					cpy(&tF[k1][k2], &sumA, n);
				}
			}
			for (int k1 = 0; k1 < 2; k1++)
			{
				for (int k2 = 0; k2 < 2; k2++)
				{
					cpy(&ansF[k1][k2], &tF[k1][k2], n);
				}
			}
		}
		k >>= 1;
	}

	cpy(&tA, &powF[0][0][0], n);
	for (int i = 0; i < n; i++)
	{
		tA.e[i][i] = m - 1;//防止出现负数
	}
	add(&ansF[1][0], &tA, &ansF[1][0], n, m);

	output(&ansF[1][0], n);

	return 0;
}

//(n 阶矩阵对 m 取模) 把 x * y 输出至 res
void mult(Matrix * x, Matrix * y, Matrix * res, int & n, int & m)
{
	static Matrix tA;
	static int sum;

	for (int k1 = 0; k1 < n; k1++)
	{
		for (int k2 = 0; k2 < n; k2++)
		{
			sum = 0;
			for (int j = 0; j < n; j++)
			{
				sum += x->e[k1][j] * y->e[j][k2];
			}
			tA.e[k1][k2] = sum % m;
		}
	}

	for (int k1 = 0; k1 < n; k1++)
	{
		for (int k2 = 0; k2 < n; k2++)
		{
			res->e[k1][k2] = tA.e[k1][k2];
		}
	}

	return;
}

//(n 阶矩阵对 m 取模) 把 x + y 输出至 res
void add(Matrix * x, Matrix * y, Matrix * res, int & n, int & m)
{
	static Matrix tA;

	for (int k1 = 0; k1 < n; k1++)
	{
		for (int k2 = 0; k2 < n; k2++)
		{
			tA.e[k1][k2] = x->e[k1][k2] + y->e[k1][k2];
		}
	}

	for (int k1 = 0; k1 < n; k1++)
	{
		for (int k2 = 0; k2 < n; k2++)
		{
			res->e[k1][k2] = tA.e[k1][k2] % m;
		}
	}

	return;
}

//(n 阶矩阵) 把 x 拷贝至 tar
void cpy(Matrix * tar, Matrix * x, int & n)
{
	for (int k1 = 0; k1 < n; k1++)
	{
		for (int k2 = 0; k2 < n; k2++)
		{
			tar->e[k1][k2] = x->e[k1][k2];
		}
	}

	return;
}

//打印 n 阶矩阵 x
void output(Matrix * x, int & n)
{
	for (int k1 = 0; k1 < n; k1++)
	{
		for (int k2 = 0; k2 < n; k2++)
		{
			cout << x->e[k1][k2] << ' ';
		}
		cout << '\n';
	}

	return;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator