题目描述
题解
矩阵乘法
考虑把相同位数的数放到一起处理：
设有$k$位的数为$[l,r]$，那么枚举从大到小的第$i$个数（即枚举$r-i+1$），考虑其对$Concatenate(l..r)$的贡献：
$v_i=(r-i+1)10^{k(i-1)}$
所以要求的就是：
$\sum\limits_{i=1}^{r-l+1}(r-i+1)10^{k(i-1)}\mod m\ =\ \sum\limits_{i=0}^{r-l}(r-i)10^{ki}\mod m$
这个式子可以使用矩阵乘法解决。具体方法：
$\begin{bmatrix}(r-i)10^{ki}&10^{ki}&sum_{i-1}\end{bmatrix}*\begin{bmatrix}10^k&0&1\\-10^k&10^k&0\\0&0&1\end{bmatrix}=\begin{bmatrix}(r-i-1)10^{k(i+1)}&10^{k(i+1)}&sum_i\end{bmatrix}$
然后再乘上$10^{该位后面的位数}$即为它们对答案的贡献。把所有位数的数的贡献加起来即为答案。
注意需要unsigned long long。
#include#include #include using namespace std;typedef unsigned long long ull;int m;struct data{ ull v[3][3]; data(ull x = 0) {memset(v , 0 , sizeof(v)) , v[0][0] = v[1][1] = v[2][2] = x;} ull *operator[](int a) {return v[a];} data operator*(data a) { data ans; int i , j , k; for(i = 0 ; i < 3 ; i ++ ) for(j = 0 ; j < 3 ; j ++ ) for(k = 0 ; k < 3 ; k ++ ) ans[i][j] = (ans[i][j] + v[i][k] * a[k][j]) % m; return ans; }}a;data pow(data x , ull y){ data ans(1); while(y) { if(y & 1) ans = ans * x; x = x * x , y >>= 1; } return ans;}ull pow(ull x , ull y){ ull ans = 1; while(y) { if(y & 1) ans = ans * x % m; x = x * x % m , y >>= 1; } return ans;}int main(){ ull i , j , n , now = 1 , ans = 0; scanf("%llu%d" , &n , &m); for(i = 1000000000000000000ull , j = 19 ; i ; i /= 10 , j -- ) { if(n < i) continue; a[0][0] = a[1][1] = i % m * 10 % m , a[1][0] = (m - a[0][0]) % m , a[0][2] = a[2][2] = 1 , a[0][1] = a[1][2] = a[2][0] = a[2][1] = 0; a = pow(a , n - i + 1); ans = (ans + (n % m * a[0][2] % m + a[1][2]) * now) % m , now = now * pow(10 , j * (n - i + 1)) % m , n = i - 1; } printf("%llu\n" , ans); return 0;}