1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| 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;
}
|