题目大意：求长度为$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 
     
      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
      
       (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; }