BZOJ 2326 HNOI 2011 数学作业矩阵乘法

题目大意

求一个这样的数：“12345678910111213……”对m取模的值。

思路

观察这个数字的特点，每次向后面添加一个数。也就是原来的数乘10^k之后在加上一个数。而且处理每个数量级的时候是相似的。所以就可以用矩阵乘法来加速。我构造的矩阵是这样的。
[当前数字累加数字1]×???数量级10011001???=[新的数字累加数字+11]

CODE

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #define MO p using namespace std; 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; }

BZOJ 2326 HNOI 2011 数学作业 矩阵乘法

题目大意

思路

CODE