RT,已经调了1.5h了,样例都过了,但是就是 0 分……求调!
#include<bits/stdc++.h>
#define int1 long long
#define p 10
using namespace std;
int1 t,n = 2,nn,mm,i,j,k,e,f,ans;
int1 read(){//快读。
int1 x = 0,f = 1;
char ch = getchar();
while(!isdigit(ch)){
if(ch == '-'){
f = -1;
}
ch = getchar();
}
while(isdigit(ch)){
x = (x << 1) + (x << 3) + ch - '0';
ch = getchar();
}
return x * f;
}
void print(int1 x){//快写。
if(x < 0){
putchar('-');
x = -x;
}
if(x > 9){
print(x / 10);
}
putchar(x % 10 + 48);
return ;
}
struct owo{
int1 m[7][7];
} a,b;
owo operator^(const owo &x,const owo &y){//模拟矩阵乘法。
owo a;
for(int1 i = 1; i <= n; i++){
for(int1 j = 1; j <= n; j++){
a.m[i][j] = 0;
}
}
for(int1 i = 1; i <= n; i++){
for(int1 j = 1; j <= n; j++){
for(int1 k = 1; k <= n; k++){
a.m[i][j] += x.m[i][k] * y.m[k][j] % p;
a.m[i][j] %= p;
}
}
}
return a;
}
void mod(int1 s){
for(i = 1; i <= n; i++){
for(j = 1; j <= n; j++){
a.m[i][j] %= s;
b.m[i][j] %= s;
}
}
return ;
}
void returnx(int1 x){
for(i = 1; i <= n; i++){
for(j = 1; j <= n; j++){
a.m[i][j] = x;
b.m[i][j] = x;
}
}
return ;
}
void m_quick_pow(owo &a,owo &b,int1 k){//矩阵快速幂。
while(k > 0){
if(k & 1){
b = a ^ b;
}
a = a ^ a;
k >>= 1;
mod(p);
}
return ;
}
int1 fib(int1 k){//矩阵乘法求fib(k)。
for(i = 1; i <= n; i++){//预处理。
for(j = 1; j <= n; j++){
a.m[i][j] = (i - 1) || (j - 1);
b.m[i][j] = !((i - 1) ^ (j - 1));
}
}
m_quick_pow(a,b,k);
return b.m[2][1] % p;
}
int1 quick_pow(int1 a,int1 b,int1 s){//快速幂。
ans = 1;
while(b){
if(b & 1){
ans = a % s * ans % s;
}
a = a % s * a % s;
b >>= 1;
}
return ans % s;
}
int main(){
nn = read(),mm = read(),k = read();
if(k == 1){//不知道为什么要加的特判。
print(mm);
return 0;
}else if(k == 2){
print(nn);
return 0;
}
e = quick_pow(nn,fib(k - 2),p),f = quick_pow(mm,fib(k - 1),p);//求n^fib(k-2)%10和m^fib(f-1)%10。
print(e * f % p);
return 0;
}
明天再来看回复……