矩阵乘法模板

2019-04-13 15:10发布

站内文章 / 模拟电子
18128 0 1603
class="markdown_views prism-atom-one-light"> struct mat { int r,c; LL data[105][105]; mat() {r=c=0;memset(data,0,sizeof(data));} inline void init(int x,int y) {r=x,c=y;memset(data,0,sizeof(data));} }; mat operator *(const mat &a,const mat &b) { mat tmp;tmp.init(a.r,b.c); if (a.c!=b.r) {tmp.r=tmp.c=0;return tmp;} for (int i=0;i<=a.r;i++) { for (int j=0;j<=b.c;j++) { for (int k=0;k<=a.c;k++) tmp.data[i][j]=(tmp.data[i][j]+a.data[i][k]*b.data[k][j])%P; } } return tmp; } inline mat fastpow(int x) { mat tmp;tmp.init(m+1,m+1); for (int i=0;i<=m+1;i++) tmp.data[i][i]=1; mat base=s; while (x>0) { if (x&1) tmp=tmp*base; base=base*base; x>>=1; } return tmp; }

热门文章