递推,推得f(n) = f(n-1) + f(n-3) + f(n-4)。然后转换成矩阵相乘,如下
f(n-1) f(n-2) f(n-3) f(n-4) * 1 1 0 0 = f(n) f(n-1) f(n-2) f(n-3)
0 0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0
从而转化为快速矩阵相乘。
#include <cstdio>
#include <cstring>
#include <cstdlib> #define MATN 4 typedef struct mat_st {
int m[MATN][MATN];
mat_st() {
memset(m, , sizeof(m));
}
} mat_st; int ans[MATN]={,,,};
int mod; mat_st mult_mat(mat_st a, mat_st b) {
mat_st ret;
int i, j, k; for (i=; i<MATN; ++i) {
for (j=; j<MATN; ++j) {
for (k=; k<MATN; ++k)
ret.m[i][j] += a.m[i][k]*b.m[k][j];
ret.m[i][j] %= mod;
}
}
return ret;
} mat_st pow_mat(mat_st a, int n) {
mat_st ret;
int i; for (i=; i<MATN; ++i)
ret.m[i][i] = ; while (n) {
if (n & )
ret = mult_mat(ret, a);
a = mult_mat(a, a);
n >>= ;
}
return ret;
} int main() {
int l;
int i;
mat_st e, a; e.m[][] = e.m[][] = e.m[][] = e.m[][] = e.m[][] = e.m[][] = ;
for (i=; i<MATN; ++i)
a.m[][i] = ans[MATN--i]; while (scanf("%d %d", &l, &mod) != EOF) {
if (l <= )
printf("%d\n", ans[l]%mod);
else {
mat_st c = pow_mat(e, l-);
mat_st r = mult_mat(a, c);
printf("%d\n", r.m[][]);
#ifndef ONLINE_JUDGE
fflush(stdout);
#endif
}
} return ;
}