广义肥波

题目链接：nowcoder 214267

到主站看：https://blog.csdn.net/weixin_43346722/article/details/112726718

题目大意

定义广义斐波那契数列：
然后让你求

思路

看到题目的范围，我们可以看出应该是枚举一个 ，然后其他数的 log，大概这样的复杂度。

然后很明显枚举 可以得出 ，但是你要求的是 ， 不能取模，你总不能搞高精吧。

那我们考虑不求 ，枚举 求出 的值 。
那我们可以看出转移就是：。（就是全部运算往上诺一级）

这样就可以在取模的意义下进行而不出问题了。

代码

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define mo 1000000007

using namespace std;

ll a, b, m, re, tmp, l, r;
int n;

ll ksm(ll x, ll y) {
    re = 1ll;
    while (y) {
        if (y & 1) re = (re * x) % mo;
        x = (x * x) % mo;
        y >>= 1;
    }
    return re;
}

int main() {
    scanf("%lld %lld %lld %d", &a, &b, &m, &n);

    l = r = m;
    for (int i = 3; i <= n; i++) {
        tmp = (ksm(l, b) % mo * ksm(r, a)) % mo;
        l = r;
        r = tmp;
    }

    printf("%lld", r);

    return 0;
}