题意: xi=a⋅xi−1+b⋅xi−2 for all i≥2 求第n项取mod的值 1<n<10^(10^6) 10^9<mod<2*10^9
题解:求出 1, 2, 4, 8,次幂接下来就可以求出 10,20,40,80,100 次幂
#include <bits/stdc++.h>
#include <cstring>
#define ll long long
using namespace std;
ll mod;
struct Mat {
int n,m;
ll mem[3][3];
Mat(int n, int m) {
this->n = n, this->m = m;
memset(mem, 0, sizeof mem);
return;
}
Mat operator*(const Mat &a)const{
Mat c(n,a.m);
for (int i = 1; i <= c.n; i++) {
for (int j = 1; j <= c.m; j++) {
for (int k = 1; k <= m; k++)
c.mem[i][j] += mem[i][k] * a.mem[k][j];
c.mem[i][j] %= mod;
}
}
return c;
}
};
Mat solve(Mat a,Mat c,char *s){
Mat b = c;
for(int i=strlen(s)-1;i>=0;i--){
int cur = s[i] - '0';
while(cur--) b = b*a;
Mat tmp = a*a;
a = tmp*tmp;
a = a*a*tmp;
}
return b;
}
char s[10000000];
int main() {
ll x0,x1,a,b;
ll tmp;
Mat m1(2,2),m2(2,2);
scanf("%lld %lld %lld %lld",&x0,&x1,&a,&b);
scanf("%s %lld",s,&mod);
m1.mem[1][1] = 0;
m1.mem[1][2] = b;
m1.mem[2][1] = 1;
m1.mem[2][2] = a;
m2.mem[1][1] = x0;
m2.mem[2][1] = 0;
m2.mem[1][2] = x1;
m2.mem[2][2] = 0;
m1 = solve(m1,m2,s);
printf("%lld",m1.mem[1][1]%mod);
return 0;
}
/*
1 1 2 2
1 8
*/