[洛谷P2106]Sam数

题目大意：问长度为$n$的$Sam$数有几个，$Sam$数的定义为没有前导零，相邻两个数字之差绝对值小于等于$2$的数

题解：发现转移方程一定，可以矩阵快速幂。

卡点：没有特判$n=1$的情况

C++ Code：

#include <cstdio>
const int mod = 1e9 + 7;
inline int abs(int a) {return a < 0 ? -a : a;}
inline void up(int &a, int b) {a += b - mod; a += a >> 31 & mod;}
struct matrix {
#define M 10
int s[M][M];
inline void E() {
for (int i = 0; i < M; i++) s[i][i] = 1;
}
inline void init() {
for (int i = 0; i < M; i++) {
for (int j = 0; j < M; j++) s[i][j] = abs(i - j) <= 2;
}
}
inline friend matrix operator * (const matrix &lhs, const matrix &rhs) {
matrix res;
long long ans;
for (int i = 0; i < M; i++) {
for (int j = 0; j < M; j++) {
ans = 0;
for (int k = 0; k < M; k++) ans += static_cast<long long> (lhs.s[i][k]) * rhs.s[k][j];
res.s[i][j] = ans % mod;
}
}
return res;
}
#undef M
} ans, base;long long n;
int main() {
scanf("%lld", &n);
if (n == 1) {
puts("10");
return 0;
}
base.init();
for (int i = 1; i < 10; i++) ans.s[0][i] = 1;
for (n--; n; n >>= 1, base = base * base) if (n & 1) ans = ans * base;
int res = 0;
for (int i = 0; i < 10; i++) up(res, ans.s[0][i]);
printf("%d\n", res);
return 0;
}