题目大意
求一个这样的数：“12345678910111213……”对m取模的值。
思路
观察这个数字的特点，，每次向后面添加一个数。也就是原来的数乘10^k之后在加上一个数。而且处理每个数量级的时候是相似的。所以就可以用矩阵乘法来加速。我构造的矩阵是这样的。
CODE;long long k,p;struct Matrix{long long num[5][5];int w,h;Matrix(int _,int __):w(_),h(__) {memset(num,0,sizeof(num));}Matrix() {memset(num,0,sizeof(num));}Matrix operator *(const Matrix &a)const {Matrix re(w,a.h);for(int i = 1; i <= w; ++i)for(int j = 1; j <= a.h; ++j)for(int k = 1; k <= h; ++k)re.num[i][j] = (re.num[i][j] + num[i][k] * a.num[k][j] % MO) % MO;return re;}};inline Matrix QuickPower(Matrix a,long long k){Matrix re(3,3);re.num[1][1] = re.num[2][2] = re.num[3][3] = 1;while(k) {if(k&1) re = re * a;a = a * a;k >>= 1;}return re;}int main(){cin >> k >> p;long long now = 10,ans_num = 0;while(k >= now – now / 10 && now < 1e18) {k -= now – now / 10;Matrix right(3,3);right.num[1][1] = now % MO;right.num[2][1] = right.num[2][2] = right.num[3][2] = right.num[3][3] = 1;right = QuickPower(right,now – now / 10);Matrix left(1,3);left.num[1][1] = ans_num;left.num[1][2] = (now / 10) % MO;left.num[1][3] = 1;ans_num = (left * right).num[1][1];now *= 10;}Matrix right(3,3);right.num[1][1] = now % MO;right.num[2][1] = right.num[2][2] = right.num[3][2] = right.num[3][3] = 1;right = QuickPower(right,k);Matrix left(1,3);left.num[1][1] = ans_num;left.num[1][2] = (now / 10) % MO;left.num[1][3] = 1;cout << (left * right).num[1][1] << endl;return 0;}
在前进的路上，主动搬开别人脚下的绊脚石，有时往往也是为自己铺路。
