BZOJ 2326 HNOI 2011 数学作业 矩阵乘法
2015-03-03 14:57:53         来源：(╯°口°)╯(┴—┴

## 思路

[当前数字累加数字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;
}``````