题目大意：求长度为$n$的$01$串中，没有连续至少$3$个$1$的串的个数
题解：令$a_1$为结尾一个$1$的串个数，$a_2$为结尾两个$1$的串的个数，$b$为结尾是$0$的串的个数。$a_1=b,a_2=a_1,b=a_1+a_2+b$。
卡点：无
C++ Code：
#include <cstdio>
const int mod = 19260817;
int Tim, n;
inline void up(int &a, int b) {if ((a += b) >= mod) a -= mod;}
struct matrix {
#define M 3
int s[M][M];
inline matrix() {
for (int i = 0; i < M; i++) {
for (int j = 0; j < M; j++) s[i][j] = 0;
}
}
inline void init() {
for (int i = 0; i < M; i++) {
for (int j = 0; j < M; j++) s[i][j] = 0;
}
s[0][1] = s[0][2] = 1;
s[1][2] = 1;
s[2][0] = s[2][2] = 1;
}
inline void init(int a) {
for (int i = 0; i < M; i++) {
for (int j = 0; j < M; j++) s[i][j] = 0;
}
s[0][2] = 1;
}
inline int getans() {
int res = 0;
for (int i = 0; i < M; i++) up(res, s[0][i]);
return res;
}
inline friend matrix operator * (const matrix &lhs, const matrix &rhs) {
matrix res;
for (int i = 0; i < M; i++) {
for (int j = 0; j < M; j++) {
for (int k = 0; k < M; k++) {
up(res.s[i][j], static_cast<long long>(lhs.s[i][k]) * rhs.s[k][j] % mod);
}
}
}
return res;
}
} base, ans; int solve(int n) {
base.init();
ans.init(1);
for (; n; n >>= 1, base = base * base) if (n & 1) ans = ans * base;
return ans.getans();
}
int main() {
scanf("%d", &Tim);
while (Tim --> 0) {
scanf("%d", &n);
printf("%d\n", solve(n));
}
return 0;
}