盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码

HDU 4565 So Easy!(矩阵, 数学)

题目

源地址:http://acm.hdu.edu.cn/showproblem.php?pid=4565

题意

s=ceil( (a+sqrt(b))^n ) % m

思路

http://blog.csdn.net/crazy______/article/details/9021169

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#define pb push_back
#define INF 1 << 30
#define fi first
#define se second
#define debug puts("=====================");
using namespace std;
typedef long long ll;
const int maxn = 2;
const int maxm = 2;
int mod;
struct Matrix {
int n, m;
int a[maxn][maxm];
void clear() {
n = m = 0;
memset(a, 0, sizeof(a));
}
Matrix operator * (const Matrix &b) const { //实现矩阵乘法
Matrix tmp;
tmp.n = n;
tmp.m = b.m;
for (int i = 0; i < n; i++)
for (int j = 0; j < b.m; j++) tmp.a[i][j] = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
if (!a[i][j]) continue;
for (int k = 0; k < b.m; k++)
tmp.a[i][k] += a[i][j] * b.a[j][k], tmp.a[i][k] %= mod;
}
return tmp;
}
void Copy(const Matrix &b) {
n = b.n, m = b.m;
for (int i = 0; i < n; i++)
for(int j = 0; j < m; j++) a[i][j] = b.a[i][j];
}
void unit(int sz) {
n = m = sz;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) a[i][j] = 0;
a[i][i] = 1;
}
}
};
Matrix A, B;
int a, b, n;
void init() {
A.clear(); //矩阵A是构造的矩阵
A.n = A.m = 2;
A.a[0][0] = 2 * a % mod;
A.a[0][1] = (-(a * a - b) % mod + mod) % mod;
A.a[1][0] = 1;
A.a[1][1] = 0;
B.clear();
B.n = 2;
B.m = 1;
B.a[0][0] = 2 * a % mod;
B.a[1][0] = 2;
}
Matrix Matrix_pow(Matrix A, int k, int mod) { //矩阵快速幂
Matrix res;
res.clear();
res.n = res.m = 2;
for (int i = 0; i < 2; i++) res.a[i][i] = 1;
while(k) {
if (k & 1) res.Copy(A * res);
k >>= 1;
A.Copy(A * A);
}
return res;
}
int main () {
while(~scanf("%d%d%d%d", &a, &b, &n, &mod)) {
init();
A = Matrix_pow(A, n - 1, mod);
A = A * B;
printf("%d\n", A.a[0][0]);
}
return 0;
}