A Simple Math Problem(矩阵快速幂)----------------------蓝桥备战系列

Lele now is thinking about a simple function f(x).

If x < 10 f(x) = x.

If x >= 10 f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10);

And ai(0<=i<=9) can only be 0 or 1 .

Now, I will give a0 ~ a9 and two positive integers k and m ,and could you help Lele to caculate f(k)%m.

Input

The problem contains mutiple test cases.Please process to the end of file.

In each case, there will be two lines.

In the first line , there are two positive integers k and m. ( k<2*10^9 , m < 10^5 )

In the second line , there are ten integers represent a0 ~ a9.

Output

For each case, output f(k) % m in one line.

Sample Input

10 9999

1 1 1 1 1 1 1 1 1 1

20 500

1 0 1 0 1 0 1 0 1 0

Sample Output

45

104

代码：

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<queue>

#include<stack>

#include<set>

#include<vector>

#include<map>

#include<cmath>

const int maxn=1e5+5;

typedef long long ll;

using namespace std;

ll mod;

ll op[15];

struct mat

{

	ll a[15][15];

};

mat Mul(mat a,mat b)

{

	mat ans;

	memset(ans.a,0,sizeof(ans.a));

	for(int t=0;t<10;t++)

	{

		for(int j=0;j<10;j++)

		{

			for(int k=0;k<10;k++)

			{

				ans.a[t][j]=(ans.a[t][j]+a.a[t][k]*b.a[k][j])%mod;

			}

		}

	}

	return ans;

}

mat ans;

ll quick(ll n)

{

	mat res;

	memset(res.a,0,sizeof(res.a));

	for(int t=0;t<10;t++)

	{

		res.a[0][t]=op[t];

	}

	res.a[1][0]=1;

	res.a[2][1]=1;

	res.a[3][2]=1;

	res.a[4][3]=1;

	res.a[5][4]=1;

	res.a[6][5]=1;

	res.a[7][6]=1;

	res.a[8][7]=1;

	res.a[9][8]=1;

	while(n)

	{

		if(n&1)

		{

			ans=Mul(res,ans);

		}

		res=Mul(res,res);

		n>>=1;

	}

	return ans.a[0][0];

}

int main()

{

	ll n;

	while(cin>>n)

	{

		cin>>mod;

		for(int t=0;t<10;t++)

		{

			scanf("%lld",&op[t]);

		}

		if(n<10)

		{

			printf("%lld\n",n%mod);

		}

		else{

		for(int t=9;t>=0;t--)

		{

			ans.a[9-t][0]=t;

		}

		printf("%lld\n",quick(n-9)%mod);

	    }

	}

   return 0;

}

巴特西

A Simple Math Problem(矩阵快速幂)----------------------蓝桥备战系列

最新文章

热门文章