题意比较简单,就是要求,显然有,看到这里,那就简单了,递推式,加矩阵,矩阵快速幂无疑了嘛,所以我们开始构造矩阵。
显然有如下矩阵,是单位矩阵,是输入矩阵,是零矩阵。
通过这个矩阵的递推,我们就可以通过快速幂,达到快速求解的目的。
我严重怀疑这道题目数据有问题,就,然后就过了???
/*
Author : lifehappy
*/
// #pragma GCC optimize(2)
// #pragma GCC optimize(3)
// #include <bits/stdc++.h>
#include <cstdio>
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <cmath>
#define mp make_pair
#define pb push_back
#define endl '\n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const double pi = acos(-1.0);
const double eps = 1e-7;
const int inf = 0x3f3f3f3f;
inline ll read() {
ll f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
return f * x;
}
void print(ll x) {
if(x < 10) {
putchar(x + 48);
return ;
}
print(x / 10);
putchar(x % 10 + 48);
}
const int N = 70;
int n, k, mod;
struct matrix {
int a[N][N];
matrix operator * (const matrix & t) const {
matrix temp;
for(int i = 1; i <= 2 * n; i++) {
for(int j = 1; j <= 2 * n; j++) {
temp.a[i][j] = 0;
for(int k = 1; k <= 2 * n; k++) {
temp.a[i][j] = (temp.a[i][j] + a[i][k] * t.a[k][j]) % mod;
}
}
}
return temp;
}
}E, A, O;
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
n = read(), k = read(), mod = read();
matrix fat, ans;
for(int i = 1; i <= 2 * n; i++) {//先置零,
for(int j = 1; j <= 2 * n; j++) {
fat.a[i][j] = ans.a[i][j] = 0;
}
}
for(int i = 1; i <= n; i++) {//读入的时候置A加上置E矩阵。
for(int j = 1; j <= n; j++) {
fat.a[i + n][j + n] = ans.a[i + n][j] = read();
}
fat.a[i][i] = fat.a[i][i + n] = 1;
}
while(k) {
if(k & 1) ans = fat * ans;
fat = fat * fat;
k >>= 1;
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
printf("%d%c", ans.a[i][j], j == n ? '\n' : ' ');
}
}
return 0;
}
写了一手逼格高一点的举证套矩阵的重载操作符的写法,可是太菜了,调不出来
/*
Author : lifehappy
*/
// #pragma GCC optimize(2)
// #pragma GCC optimize(3)
// #include <bits/stdc++.h>
#include <cstdio>
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <cmath>
#define mp make_pair
#define pb push_back
#define endl '\n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const double pi = acos(-1.0);
const double eps = 1e-7;
const int inf = 0x3f3f3f3f;
inline ll read() {
ll f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
return f * x;
}
void print(ll x) {
if(x < 10) {
putchar(x + 48);
return ;
}
print(x / 10);
putchar(x % 10 + 48);
}
const int N = 70;
int n, k, mod;
struct matrix {
int a[N][N];
matrix operator * (const matrix & t) const {
matrix temp;
for(int i = 1; i <= 2 * n; i++) {
for(int j = 1; j <= 2 * n; j++) {
temp.a[i][j] = 0;
for(int k = 1; k <= 2 * n; k++) {
temp.a[i][j] = (temp.a[i][j] + a[i][k] * t.a[k][j]) % mod;
}
}
}
return temp;
}
matrix operator + (const matrix & t) const {
matrix temp;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
temp.a[i][j] = (a[i][j] + t.a[i][j]) % mod;
}
}
return temp;
}
}E, A, O;
struct Matrix {
matrix a[3][3];
Matrix operator * (const Matrix & t) const {
Matrix temp;
for(int i = 1; i <= 2; i++) {
for(int j = 1; j <= 2; j++) {
temp.a[i][j] = O;
for(int k = 1; k <= 2; k++) {
temp.a[i][j] = (a[i][k] * t.a[k][j]) + temp.a[i][j];
}
}
}
}
};
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
n = read(), k = read(), mod = read();
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
A.a[i][j] = read();
E.a[i][j] = O.a[i][j] = 0;
}
E.a[i][i] = 1;
}
Matrix fat, ans;
fat.a[1][1] = E, fat.a[1][2] = E, fat.a[2][1] = O, fat.a[2][2] = A;
ans.a[1][1] = O, ans.a[1][2] = O, ans.a[2][1] = A, ans.a[2][2] = O;
while(k) {
if(k & 1) ans = ans * fat;
fat = fat * fat;
k >>= 1;
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
printf("%d%c", ans.a[1][1].a[i][j], j == n ? '\n' : ' ');
}
}
return 0;
}
本文地址:https://blog.csdn.net/weixin_45483201/article/details/107555663
如对本文有疑问, 点击进行留言回复!!
Android进程通信(AIDL快速实现inder进程通信)
Android开发使用SimpleAdapter与ListView列表展示增加头和尾
Execution failed for task ‘:app:checkDebugDuplicateClasses‘解决方案
Cleartext HTTP traffic to pic1.win4000.com not permitted不允许明文http访问解决
Android SDK 26以后ant编译错误解决办法(错误信息:taskdef A class needed by class com.android.ant.GetUiTargetTask)
android8.1 mtk camera hal各种操作流程
Android 软键盘在有scollview,纵向viewpager+recyclview实现列表,或者recyclview, 把布局顶上去的问题,保证背景不会发生变化
网友评论