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

矩阵套矩阵+快速幂

Posted by Ioencgc at 2023-07-23 18:21:23 on Problem 3233
#include<iostream>
#include<stack>
#include<string.h>
#include<cmath>
#include<iomanip>
#include<algorithm>
#include<climits>
#include<cstdio>
#include<vector>
#include<sstream>
#include<ctype.h>
#include<set>
#include<map>
#include<ctime>
#include<stdlib.h>
#include<queue>
#include<bitset>
#define ll long long
#define inf INT_MAX
using namespace std;
template<typename TTT>inline void mr(TTT& theNumberToRead)
{
	theNumberToRead = 0;
	bool prn = false;
	char c = getchar();
	while (!isdigit(c))
	{
		if (c == '-')prn = true;
		c = getchar();
	}
	while (isdigit(c))
		theNumberToRead = 10 * theNumberToRead + (c ^ 48), c = getchar();
	if (prn)
		theNumberToRead = -theNumberToRead;
}
template<typename TTT>inline TTT mrr()
{
	TTT theNumberToRead = 0;
	bool prn = false;
	char c = getchar();
	while (!isdigit(c))
	{
		if (c == '-')prn = true;
		c = getchar();
	}
	while (isdigit(c))
		theNumberToRead = 10 * theNumberToRead + (c ^ 48), c = getchar();
	return prn ? -theNumberToRead : theNumberToRead;
}
template<typename T>void my_write(T x)
{
	if (x)
		my_write(x / 10),
		putchar(x % 10 ^ 48);
}
template<typename T>void mw(T x, char mid)
{
	if (x)
	{
		if (x < 0)
			putchar('-'),
			x = -x;
		my_write(x);
	}
	else putchar(48);
	if (mid)
		putchar(mid);
}
// ******************************************华丽的分割线******************************************
// ******************************************华丽的分割线******************************************
// ******************************************华丽的分割线******************************************
// ******************************************华丽的分割线******************************************
// ******************************************华丽的分割线******************************************
typedef vector<int> vec;
typedef vector<vec> mat;
int mod;
mat mul(mat& a, mat& b)
{
	mat c(a.size(), vec(b[0].size()));
	for (int i = 0; i < a.size(); ++i)
		for (int j = 0; j < b[0].size(); ++j)
			for (int k = 0; k < b.size(); ++k)
				c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod;
	return c;
}
mat fast_pow(mat a, int n)
{
	mat b(a.size(), vec(a.size()));
	for (int i = 0; i < b.size(); ++i)
		b[i][i] = 1;
	while (n)
	{
		if (n & 1)
			b = mul(b, a);
		a = mul(a, a);
		n >>= 1;
	}
	return b;
}
int main()
{
	int n, k;
	mr(n), mr(k), mr(mod);
	mat a(n << 1, vec(n << 1));
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
			mr(a[i][j]), a[n + i][j] = a[i][j];
		a[n + i][n + i] = 1;
	}
	a = fast_pow(a, k);
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			mw(a[n + i][j], " \n"[j + 1 == n]);
	return 0;
}

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