A Simple Math Problem

【题目链接】A Simple Math Problem

【题目类型】矩阵快速幂

&题解：

这是一个模板题,也算是入门了吧. 推荐一个博客:点这里 跟着这个刷,应该就可以了

&代码：

#include <cstdio>

#include <iostream>

#include <set>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <map>

#include <queue>

#include <vector>

using namespace std;

#define INF 0x3f3f3f3f

using ll=long long;

typedef vector<ll> vec;

typedef vector<vec> mat;

const int maxn= 10 +9;

ll k,m,a[maxn];

mat mul(mat &A,mat &B)

{

	mat C(A.size(),vec(B[0].size()));

	for(int i=0;i<A.size();i++)

	for(int k=0;k<B.size();k++)

	for(int j=0;j<B[0].size();j++){

		C[i][j]=(C[i][j]+A[i][k]*B[k][j])%m;

	}

	return C;

}

mat bin_pow(mat A,ll n)

{

	int si=A.size();

	mat B(si,vec(si));

	for(int i=0;i<si;i++)

		B[i][i]=1;

	while(n>0){

		if(n&1)

			B=mul(B,A);

		A=mul(A,A);

		n>>=1;

	}

	return B;

}

int main()

{

	freopen("E:1.txt","r",stdin);

	while(cin>>k>>m){

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

			cin>>a[i];

		mat A(10,vec(10));

		for(int i=0;i<10;i++){

			A[0][i]=a[i];

			if(i>0) A[i][i-1]=1;

		}

		if(k<10) cout<<k<<endl;

		else{

			A=bin_pow(A,k);

//		for(auto i:A){

//			for(auto j:i)

//				cout<<j<<" ";

//			cout<<endl;

//		}

			ll ans=0;

			for(int i=0;i<10;i++){

				ans=(ans+A[9][i]*(9-i))%m;

			}

			cout<<ans<<endl;

		}

	}

	return 0;

}