改过了```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;
#define int long long
ll n , m;
int mul(int a, int b){int res = 0; for(; b; b >>= 1, a = (a % m + a % m) % m) if(b & 1) res = (res + a) % m;return res;}
struct Martix
{
ll f[4][4];
friend Martix operator * (const Martix & a,const Martix & b)
{
Martix res;
memset(res.f,0,sizeof res.f);
for(int k = 1;k <= 3;k ++)
for(int i = 1;i <= 3;i ++)
for(int j = 1;j <= 3;j ++)
res.f[i][j] = (res.f[i][j] + a.f[i][k] % m * b.f[k][j] % m) % m;
return res;
}
}ans , e;
Martix ksm(Martix a,ll b)
{
Martix res;
memset(res.f,0,sizeof res.f);
for(int i = 1;i <= 3; i++)
res.f[i][i] = 1;
while(b)
{
if(b & 1) res = a * res;
a = a * a;
b >>= 1;
}
return res;
}
ll fuck()
{
ans.f[1][3]=1;
e.f[2][1] = 1;
e.f[2][2] = 1;e.f[3][1] = 1;
e.f[3][2] = 1;e.f[3][3] = 1;
for(ll tmp = 1; tmp <= n; tmp *= 10) {
e.f[1][1] = tmp * 10%m;
ans = ans * ksm(e,(min((tmp*10)-1,n)-tmp+1));
}
return ans.f[1][1] % m;
}
signed main()
{
scanf("%lld%lld",&n,&m);
printf("%lld",fuck() % m);
return 0;
}
```
by g_ws @ 2019-06-07 20:34:08
[这是过了的]( https://www.luogu.org/paste/0zoyc0c4 )
by g_ws @ 2019-06-07 20:35:44