矩阵乘法优化dp
O(n) 递推十分显然
(f[i] = f[i - 1] * 10 ^ {lg10(i)} + i)
然后考虑矩乘
初始矩阵就是
[egin{Bmatrix}
1 & 1 & 1
end{Bmatrix}
]
然后转移矩阵是
[ egin{Bmatrix}
10^k & 0 & 0 \
1 & 1 & 0 \
1 & 1 & 1
end{Bmatrix}
]
我们发现一个问题
就是转移矩阵的第((1,1))位是会变化的
所以我们按照十进制下的每一位单独建转移矩阵跑矩乘
每次更新转移矩阵后都用初始矩阵去乘
思路说起来好像挺简单
然后一堆细节让我调了半个下午
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
# define int unsigned long long
using namespace std ;
int n , mod , pw[25] ;
struct Mat {
int f[4][4] ;
inline void clear() { memset(f , 0 , sizeof(f)) ; }
inline void Begin()
{ for(int i = 1 ; i <= 3 ; i ++) f[i][i] = 1 ; }
} st , a ;
inline Mat operator * (Mat x , Mat y) {
Mat temp ; memset(temp.f , 0 , sizeof(temp.f)) ;
for(int i = 1 ; i <= 3 ; i ++)
for(int j = 1 ; j <= 3 ; j ++)
for(int k = 1 ; k <= 3 ; k ++)
temp.f[i][j] = (temp.f[i][j] + x.f[i][k] * y.f[k][j]) % mod ;
return temp ;
}
inline Mat fpw(Mat Base , int k) {
Mat temp = st ;
while(k) {
if(k & 1) temp = temp * Base ;
Base = Base * Base ; k >>= 1 ;
}
return temp ;
}
inline int Solve() {
st.f[1][1] = st.f[1][2] = st.f[1][3] = 1 ;
for(int w = 10 , pre = 0 ; pre < n ; w *= 10) {
a.f[1][1] = w % mod ; a.f[1][2] = 0 ; a.f[1][3] = 0 ;
a.f[2][1] = 1 ; a.f[2][2] = 1 ; a.f[2][3] = 0 ;
a.f[3][1] = 1 ; a.f[3][2] = 1 ; a.f[3][3] = 1 ;
st = fpw(a , min(w - 1 , n) - pre - (w <= 10)) ; pre = w - 1 ;
}
return st.f[1][1] ;
}
# undef int
int main() {
# define int long long
cin >> n >> mod ;
cout << Solve() << endl ;
return 0 ;
}