首先，列方程

我们定义s[i] = 10 ^ ((int) log(i))

于是，f[i] = (f[i - 1] * s[i] + i) % p

反正总之就是个沙茶递推

然后我们来看优化。。。怎么感觉像矩阵乘法呢？

发现要按照log(i)即i的位数分类讨论，在相同位数的时候令矩阵为

s[i]  0    0

 1    1    0

 0    1    1

即可

 

1 /************************************************************** 2     Problem: 2326 3     User: rausen 4     Language: C++ 5     Result: Accepted 6     Time:16 ms 7     Memory:808 kb 8 ****************************************************************/ 9  10 #include 
      
       11  12 using namespace std;13 typedef long long ll;14  15 ll n, p;16  17 struct Matrix {18     ll x[4][4];19      20     Matrix (int X) {21         int i, j;22         for (i = 1; i <= 3; ++i)23             for (j = 1; j <= 3; ++j)24                 if (i == j) x[i][j] = X;25                 else x[i][j] = 0;26     }27      28     ll* operator [] (int X) {29         return x[X];30     }31 };32  33 inline void operator *= (Matrix &x, Matrix y) {34     int i, j, k;35     Matrix res(0);36     for (i = 1; i <= 3; ++i)37         for (j = 1; j <= 3; ++j)38             for (k = 1; k <= 3; ++k)39                 (res[i][j] += x[i][k] * y[k][j]) %= p;40     x = res;41 };42  43 Matrix pow(Matrix x, ll y) {44     Matrix res(1);45     while (y) {46         if (y & 1) res *= x;47         x *= x, y >>= 1;48     }49     return res;50 }51  52 int main() {53     ll i;54     Matrix ans(1), a(0);55     scanf("%lld%lld", &n, &p);56     a[1][1] = 10 % p, a[2][1] = a[2][2] = a[3][2] = a[3][3] = 1;57     for (i = 10; i <= n; i *= 10, a[1][1] = i % p)58         ans *= pow(a, i - i / 10);59     ans *= pow(a, n - i / 10 + 1);60     printf("%lld\n", (ans[2][1] + ans[3][1]) % p);61     return 0;62 }