P7318 「PMOI-4」人赢の梦

标签：PMOI int ll 矩阵 base P7318 ans 数列

这个得先了解用矩阵求斐波那契数列：
详细点这里
很多方法，最简单的就是找循环节（前面写挂好几次 悲），还有就是矩阵。
对于题目，我们发现有下列数列：

\[n,m,nm,nm^2,n^2m^3,n^3m^5,n^5m^8,n^8m^{13} \]

从第四项开始，\(n\),\(m\)的次数都是有规律的：斐波那契数列。
快速幂矩阵乘所求的斐波那契数列为：

\[1,2,3,5,8,13,21,34,55,89 \]

但是实现好像出了点问题：

#include <bits/stdc++.h>
#define ll long long
#define re register
using namespace std;
const int N=800, INF=0x3f3f3f3f;
ll n,m,k;
ll ans[3][3];
ll a[3][3];
void f1(){//ans=a*ans
	ll A[3][3]={0};
	for(int i=1;i<=2;i++)
		for(int j=1;j<=2;j++)
			for(int k=1;k<=2;k++){
				A[i][j]+=a[i][k]*ans[k][j]%100000;
				A[i][j]%=100000;
			}
	for(int i=1;i<=2;i++)
		for(int j=1;j<=2;j++)
			ans[i][j]=A[i][j]%100000;
}
void f2(){//a=a*a
	ll A[3][3]={0};
	for(int i=1;i<=2;i++)
		for(int j=1;j<=2;j++)
			for(int k=1;k<=2;k++){
				A[i][j]+=a[i][k]*a[k][j]%100000;
				A[i][j]%=100000;
			}
	for(int i=1;i<=2;i++)
		for(int j=1;j<=2;j++)
			a[i][j]=A[i][j]%100000;
}
ll FIB(ll  x){
	x--;
	for(int i=1;i<=2;i++)ans[i][i]=1;
	a[1][1]=1;a[1][2]=1;a[2][1]=1;a[2][2]=0;
	while(x>0){
		if(x&1)f1();
		f2();
		x>>=1;
	}
	ll r=ans[1][1]+ans[1][2];
	return r;
}
ll QP(ll x,ll y){
	ll base=x,ans=1;
	while(y>0){
		if(y&1){
			ans*=base;
			ans%=10;
		}
		base*=base;
		base%=10;
		y>>=1;
	}
	return ans;
}
int main(){
	cin>>n>>m>>k;
	if(k==1){
		cout<<n<<endl;
		return 0;
	}
	if(k==2){
		cout<<m<<endl;
		return 0;
	}
	ll p,q;
	if(k==3)p=1;
	else p=FIB(k-3);
	q=FIB(k-2);
	cout<<QP(n,p)*QP(m,q)%10<<endl;
	return 0;
}

WA了四个。不知道为什么，基本实现应该是没有问题的。
UNKNOWN！！！

标签：PMOI,int,ll,矩阵,base,P7318,ans,数列
From： https://www.cnblogs.com/FaceLuck/p/17549049.html