矩阵快速幂+快速幂,但是抱灵了。
查看原帖
矩阵快速幂+快速幂,但是抱灵了。
510555
ImposterAnYu楼主2022/4/14 20:59

RT,已经调了1.5h了,样例都过了,但是就是 00 分……求调!

评测记录。

#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;
}

明天再来看回复……

2022/4/14 20:59
加载中...