矩阵快速幂

题目：

Given a number n, you should calculate 123456... 11121314... n module 11

Input

A single line with an integer n (0 < n ≤ 10¹⁸)

Output

Output one integer, 123456... 11121314... nmodule 11

Note

思路：

首先写出递推式。（如图）

然后运用矩阵快速幂求解

AC代码：

#include<bits/stdc++.h>
using namespace std;

const int mod=11;

typedef struct MATRIX
{
	int a[3][3];
}matrix;

matrix mul(matrix x,matrix y)
{
	matrix z;
	memset(z.a,0,sizeof(z.a));
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			for(int k=0;k<3;k++)
			{
				z.a[i][j]+=(x.a[i][k]*y.a[k][j])%mod;
				z.a[i][j]%=mod;
			}
	return z;
}

matrix ksm(matrix x,long long k)
{
	matrix z;
	memset(z.a,0,sizeof(z.a));
	z.a[0][0]=z.a[1][1]=z.a[2][2]=1;
	if(k==0)
		return z;
	if(k==1)
		return x;
	if(k%2==0)
	{
		z=ksm(x,k/2);
		return mul(z,z);
	}
	else
	{
		z=ksm(x,k-1);
		return mul(z,x);
	}
}

int cal(long long n)
{
	int len=0;
	while(n)
	{
		n/=10;
		len++;
	}
	return len;
}

int main()
{
	long long n;
	matrix s;
	s={{{1,0,0},{1,0,0},{1,0,0}}};
	matrix c[2];
	c[0]={{{1,1,1},{0,1,1},{0,0,1}}},
	c[1]={{{10,1,1},{0,1,1},{0,0,1}}};
	scanf("%lld",&n);
	int len=cal(n);
	matrix t;
	memset(t.a,0,sizeof(t.a));
	long long k=1;
	for(int i=1;i<len;i++)
	{
		if(i==1)
			t=ksm(c[1],8);
		else
			t=mul(ksm(c[i%2],k*9),t);	
		k*=10;	
	}
	
	if(len>1)
		t=mul(mul(ksm(c[len%2],n-k+1),t),s);
	else
		t=mul(ksm(c[1],n-1),s);
	printf("%d\n",t.a[0][0]);
	
	return 0;
}