旺崽的博客

要么天赋异禀，要么天道酬勤

0%

牛客练习赛75 A.广义肥波

发表于 分类于 Valine：

题目链接

题目描述

广义肥波那契数列，以递归的方法定义如下：

$\begin{cases}f1=1\f_2=1\f_n=a\cdot f{n-1}+b\cdot f_{n-2}(n\ge 3, n\in \mathbb Z)\end{cases}$

例如，当 $a=b=\text 1$ 时，数列为 $[\text 1,1,2,3,5,8,13,…]$。
现在，请求出 $m^{f_n}$。

输入描述:

输入共一行,包含 $\text 4$ 个正整数 $a,b,m,n(1\le a,b,m\le 10^9,1\le n \le 10^5)$

输出描述:

输出共一行，包含一个非负整数表示答案。由于结果可能较大，你只需要输出答案对 $10^9+7=1,000,000,007$ 取模的结果。

示例1

输入

1
1 1 2 4

输出

1
8

求斐波那契数列就是简单的矩阵快速幂了，但是题目设了一个小坑，就是 $a^b\% mod$，显然你的幂数和底数的模数是不一样的，而 $mod=10^9+7$，模数恰为素数，所以根据欧拉降幂，$a^b\%mod=a^{b\%(mod-1)}\% mod$，很多人可能意识到了矩阵快速幂，但是忽略了这个，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
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
ll mod = 1e9 + 7, n, K, A, B, m, mod1 = 1e9 + 6;

ll power(ll a, ll b) { return b ? power(a * a % mod, b / 2) * (b % 2 ? a : 1) % mod : 1; }

struct mat {
    ll m[2][2];
};

mat mul(mat a, mat b) {
    mat c;
    memset(c.m, 0, sizeof(c.m));
    for (int i = 0; i < n; i++) {
        for (int k = 0; k < n; k++) {
            if (a.m[i][k] == 0) continue;
            for (int j = 0; j < n; j++) {
                c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j]) % mod1;
                if (c.m[i][j] < 0) c.m[i][j] += mod1;
            }
        }
    }
    return c;
}

mat mat_pow(mat a, int k) {
    mat ans;
    ans.m[0][0] = 1, ans.m[1][0] = 1;
    ans.m[0][1] = ans.m[1][1] = 0;
    while (k > 0) {
        if (k & 1) ans = mul(a, ans);
        a = mul(a, a);
        k >>= 1;
    }
    return ans;
}


int main() {
    n = 2;
    cin >> A >> B >> m >> K;
    mat a;
    a.m[0][0] = A, a.m[0][1] = B;
    a.m[1][0] = 1, a.m[1][1] = 0;
    if (K <= 2) cout << m;
    else {
        mat ans = mat_pow(a, K - 2);
        ll u = ans.m[0][0];
        cout << power(m, u);
    }
    return 0;
}