题目链接

题干

题目大意

  1. 给你四个数: x0, x1, a, b 都>=1 <=1e9
  2. x(i) = a * x (i - 1) + b * x(i - 2) i >= 2
  3. 给你两个数: n, mod. 1<=n<=10 ^ (10 ^ 6) (超大) 1e9 <= mod <= 2e9
  4. 输出x(n)

思路

用十进制快速幂, tql
时间复杂度是 10 ^ 6 * log 10
变换矩阵也很好推

变换矩阵
具体看代码

AC代码

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
89
//#include <bits/stdc++.h>
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

#define esp 1e-6
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const int N = 1e2 + 5;
const int M = 1e9 + 5;;

int mod;
struct Matrix{
ll m[3][3];
}unit;

Matrix mul(Matrix a, Matrix b, int n, int m){ // a * b n为a的行数, m为b的列数
Matrix c;
memset(c.m, 0, sizeof c.m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
for (int k = 1; k <= n; k++)
c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j]) % mod ; // 取模在这里取
return c;
}

Matrix q_pow2(Matrix a, ll b, int n) { // a^b n为矩阵大小
Matrix ans = unit;
while(b){
if (b & 1)
ans = mul(ans, a, n, n);
a = mul(a, a, n, n);
b >>= 1;
}
return ans;
}

Matrix q_pow_10(Matrix a, string b, int n){
Matrix ans = unit;
int len = b.length();
for (int i = len - 1; i >= 0; i--){
int num = b[i] - '0';
ans = mul(ans, q_pow2(a, num, n), n, n);
a = q_pow2(a, 10, n);
}
return ans;
}
int main(){
unit.m[1][1] = unit.m[2][2] = 1;
Matrix A, B, C;
string s;
int x0, x1, a, b;
cin >> x0 >> x1 >> a >> b >> s >> mod;
A.m[1][1] = a;
A.m[1][2] = b;
A.m[2][1] = 1;
A.m[2][2] = 0;
B.m[1][1] = x1;
B.m[2][1] = x0;
int len = s.length();
if (len == 1 && s[0] == '1'){
cout << x1 << "\n";
return 0;
}


// 将s减1
while(len--){
if (s[len] != '0'){
s[len] --;
break;
}
else
s[len] = '9';
}
if (s[0] == '0')
s.erase(0, 1);



A = q_pow_10(A, s, 2);
A = mul(A, B, 2, 1);
cout << A.m[1][1] << "\n";
return 0;
}
1
恰似你一低头的温柔,娇弱水莲花不胜寒风的娇羞, 我的心为你悸动不休。  --mingfuyan