十进制矩阵快速幂-B

题意：

给你六个个数字，
求对取余

，

思路：

求广义斐波那契数列的第项，因为比较大，需要去找循环节，或者二进制转十进制运算，后者不注意容易T，但是我只会十进制，广义斐波那契数列的循环节是神仙找的规律。类比二进制的快速幂，有如下例子：

设，则：
1、
2、
3、
4、

MyCode：

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
int mod;
char str[1000007];
struct node {
    ll mat[2][2];
    node() {
        memset(mat,0,sizeof mat);
    }
    void one() {
        mat[0][0]=mat[1][1]=1;
    }
    node operator*(node other) {
        node res;
        for(int i=0; i<2; ++i)
            for(int j=0; j<2; ++j)
                for(int k=0; k<2; ++k) {
                    res.mat[i][j]+=mat[i][k]*other.mat[k][j];
                    res.mat[i][j]%=mod;
                }
        return res;
    }
};
inline node power(node a,int b) {
    node res;
    res.one();
    while(b) {
        if(b&1) res=res*a;
        a=a*a;
        b>>=1;
    }
    return res;
}
node qpow(node a,int b) {
    node res;
    res.one();
    for(int i=b-1; ~i; --i) {
        res=res*power(a,str[i]-'0');
        node tmp=a*a;
        tmp=tmp*tmp*a;
        a=tmp*tmp;
    }
    return res;
}
int main() {
    int len,x0=read(),x1=read(),a=read(),b=read();
    scanf("%s%d",str,&mod);
    len=strlen(str);
    for(int i=len-1; ~i; --i) {
        if(str[i]=='0') str[i]='9';
        else {
            --str[i];
            break;
        }
    }
    node tmp;
    tmp.mat[0][0]=a;
    tmp.mat[1][0]=b;
    tmp.mat[0][1]=1;
    node ans=qpow(tmp,len);
    printf("%lld\n",((x1*ans.mat[0][0]%mod)+(x0*ans.mat[1][0]%mod))%mod);
}