题意：

已知 \(X_i = a * X_{i - 1} + b * X_{i - 2}\)，现给定\(X_0，X_1，a，b\)，询问\(X^n \mod p\)，其中\(n <= 10^{1e6}\)

思路：

显然这道题需要用到矩阵快速幂，但是因为\(n\)是百万位级别，直接快速幂复杂度为\(1e6 * log10 * 4 * C1\)，超时。

所以我们可以用十进制矩阵快速幂，和二进制类似，复杂度为\(1e6 * 4 * C2\)。因为这里的\(n\)比较大，所以\(C2 < log10 * C1\)大概率发生。

代码：

#include<map>

#include<set>

#include<queue>

#include<cmath>

#include<stack>

#include<ctime>

#include<string>

#include<vector>

#include<cstdio>

#include<cstring>

#include<sstream>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int maxn = 1e6 + 5;

const int INF = 0x3f3f3f3f;

const ull seed = 11;

const int MOD = 1e9 + 7;

using namespace std;

char s[maxn];

ll x0, x1, a, b, mod;

struct Mat{

    ll s[2][2];

    void init(){

        for(int i = 0; i < 2; i++)

            for(int j = 0; j < 2; j++)

                s[i][j] = 0;

    }

};

inline Mat pmul(Mat a, Mat b){

    Mat t;

    t.init();

    for(int i = 0; i < 2; i++){

        for(int j = 0; j < 2; j++){

            for(int k = 0; k < 2; k++){

                t.s[i][j] = (t.s[i][j] + a.s[i][k] * b.s[k][j]) % mod;

            }

        }

    }

    return t;

}

inline Mat ppow(Mat a, int b){

    Mat ret;

    ret.init();

    for(int i = 0; i < 2; i++) ret.s[i][i] = 1;

    while(b){

        if(b & 1) ret = pmul(ret, a);

        a = pmul(a, a);

        b >>= 1;

    }

    return ret;

}

inline Mat power(Mat a, char *s, int n){

    Mat ret;

    ret.init();

    for(int i = 0; i < 2; i++) ret.s[i][i] = 1;

    for(int i = n; i >= 1; i--){

        int x = s[i] - '0';

        if(x) ret = pmul(ret, ppow(a, x));

        a = ppow(a, 10);

    }

    return ret;

}

int main(){

    scanf("%lld%lld%lld%lld", &x0, &x1, &a, &b);

    scanf("%s%lld", s + 1, &mod);

    int n = strlen(s + 1);

    Mat ans, t;

    ans.init();

    ans.s[0][0] = x1, ans.s[0][1] = x0;

    t.s[0][0] = a, t.s[0][1] = 1, t.s[1][0] = b, t.s[1][1] = 0;

    t = power(t, s, n);

    ans = pmul(ans, t);

    printf("%lld\n", ans.s[0][1]);

    return 0;

}

巴特西

牛客多校第五场B generator1（十进制矩阵快速幂）题解

题意：

思路：

代码：

最新文章

热门文章