题目链接

题干

题目大意

  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