蒟阵乘法

蒟阵乘法，顾名思义，就是蒟蒻的乘法两个蒟阵相乘

公式：(a imes b,a)为(m imes k)的蒟阵(,b)为(k imes n)的蒟阵(,c[i][j]=sum_{i=1}^{k}a[i][k] imes b[k][j])

参考code:

//代码写得很丑
long long mod，maxn;
struct node
{
	long long a[maxn][maxn];
	node operator+(const node &u)const{node v;for(int i=0;i<maxn;i++)for(int j=0;j<maxn;j++){v.a[i][j]=u.a[i][j]+a[i][j];if(v.a[i][j]>=mod)v.a[i][j]-=mod;}return v;}//请忽略这一行
	node operator*(const node &u)const{node v;for(int i=0;i<maxn;i++)for(int j=0;j<maxn;j++){v.a[i][j]=0;for(int k=0;k<maxn;k++)v.a[i][j]=(v.a[i][j]+a[i][k]*u.a[k][j])%mod;}return v;}
};

蒟阵乘法有结合律，但没有交换律

蒟阵快速幂:利用蒟阵的结合律，减少所用时间

实现类似普通的快速幂，时间复杂度：(O(log_{2}n))

代码：

void ksm(long long n)
{
	while(n)
	{
		if(n&1)ans=ans*a;//a,ans为蒟阵
		a=a*a;
		n>>=1;
	}return;//答案存储在ans里
}

例：斐波拉契数列P1962

(f[1]=f[2]=1,f[n]=f[n-1]+f[n-2],)求(f[n];;mod;;1000000007(1 ext{e}9+7))的值

过程：可以用一个(1 imes2)的蒟阵来存储(f[n-1])与(f[n-2])

于是由递推式得((f[n-1],f[n-2]) imeslgroup_{1,0}^{1,1} group=(f[n],f[n-1]))

代码：

#include<stdio.h>
const long long mod=1000000007;
struct node
{
	long long a[2][2];
	node operator+(const node &u)const{node v;for(int i=0;i<=1;i++)for(int j=0;j<=1;j++){v.a[i][j]=u.a[i][j]+a[i][j];if(v.a[i][j]>=mod)v.a[i][j]-=mod;}return v;}
	node operator*(const node &u)const{node v;for(int i=0;i<=1;i++)for(int j=0;j<=1;j++){v.a[i][j]=0;for(int k=0;k<=1;k++)v.a[i][j]=(v.a[i][j]+a[i][k]*u.a[k][j])%mod;}return v;}
}a,ans;
long long ksm(int m)
{
	while(m)
	{
		if(m&1)ans=ans*a;
		a=a*a;
		m>>=1;
	}
	return ans.a[0][0];
}
int n;
int main()
{
	a.a[0][0]=1;a.a[0][1]=1;
	a.a[1][0]=0;a.a[1][1]=0;
	ans.a[0][0]=1;ans.a[0][1]=1;
	ans.a[1][0]=1;ans.a[1][1]=0;
	scanf("%d",&n);
	if(n>2)printf("%lld
",ksm(n-2));
	else printf("%d
",1);
}