A Simple Math Problem
代码语言：javascript复制//E
#include <bits/stdc .h>
#define ll long long
using namespace std;
struct Mat{
ll m[101][101];
};
int mod;
int n;
Mat a,e;
Mat mul(Mat x,Mat y){
Mat c;
for(int i=1;i<=n;i ){
for(int j=1;j<=n;j ){
c.m[i][j] = 0;
}
}
for(int i=1;i<=n;i ){
for(int j=1;j<=n;j ){
for(int k=1;k<=n;k ){
c.m[i][j] = (c.m[i][j] x.m[i][k]*y.m[k][j]%mod)%mod;
}
}
}
return c;
}
Mat pow(Mat x,ll y){
Mat ans;
for(int i=1;i<=n;i )
for(int j=1;j<=n;j )
if(i==j)ans.m[i][i] = 1;
else ans.m[i][j] = 0;
while(y){
if(y&1)ans = mul(ans,x);
x = mul(x,x);
y>>=1;
}
return ans;
}
int main(){
int m;
n = 10;
while(cin>>m>>mod)
{
for(int i=1;i<=n;i ){
for(int j=1;j<=n;j ){
a.m[i][j] = 0;
}
}
for(int i=1;i<=n;i )
cin>>a.m[1][i];
for(int i=2;i<=n;i )
a.m[i][i-1]=1;
if(m<10) cout<<m%mod;
else {
Mat res;
res = pow(a,m-9);
int ans=0;
for(int i=1;i<=n;i )
ans =res.m[1][i]*(10-i)%mod;
cout<<ans%mod<<endl;
}
}
return 0;
}
/*
10 9999
1 1 1 1 1 1 1 1 1 1
20 500
1 0 1 0 1 0 1 0 1 0
*/
