💡题解思路

✅ 问题建模

本题求长度为 $L$ 的所有 $0$-$1$ 串中，不包含子串 101 或 111 的合法串数量（设为 $K$）。不合法的串表示 DNA 被病毒感染。

总串数为 $2^L$，但 $L$ 最大为 $10^8$，不能暴力枚举，需要构造状态转移来动态规划解决。

✅ 状态机建模

我们可以构造一个有限状态自动机（DFA），用于判断当前串是否合法。

定义状态如下（根据最后两位/三位构建）：

我们构建以下 4 个状态：

$S_0$：空串或结尾为 0，合法；

$S_1$：结尾为 1；

$S_2$：结尾为 10；

$S_3$：结尾为 11；

$S_4$：结尾为 101$（非法）；

$S_5$：结尾为 111$（非法）；

但为了优化空间，我们只记录合法状态，最终发现只需要 3 个合法状态：

$dp[i][0]$：长度为 $i$，且以 0 结尾的合法串数量；

$dp[i][1]$：长度为 $i$，以 1 结尾，上一位不是 1（即只含一个 1）；

$dp[i][2]$：长度为 $i$，以 11 结尾（不再允许再接一个 1）；

这样转移方程为：

$dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2]$ （任意合法串后接 0）

$dp[i][1] = dp[i-1][0]$ （只能从 0 后接 1）

$dp[i][2] = dp[i-1][1]$ （只能从 1 后再接 1）

初始状态：

$dp[1][0] = 1$ （"0"）

$dp[1][1] = 1$ （"1"）

$dp[1][2] = 0$

✅ 快速矩阵幂优化

由于 $L$ 很大，可使用矩阵快速幂优化计算。状态转移矩阵如下：

[ 1 1 1 1 0 0 0 1 0 ] ​

1 1 0 ​

1 0 1 ​

1 0 0 ​

​

初始列向量为：

[ 1 1 0 ] ​

1 1 0 ​

​

最终答案是第 $L$ 次幂的矩阵与初始向量相乘的第一项之和：

𝑑 𝑝 [ 𝐿 ] [ 0 ] + 𝑑 𝑝 [ 𝐿 ] [ 1 ] + 𝑑 𝑝 [ 𝐿 ] [ 2 ] dp[L][0]+dp[L][1]+dp[L][2]

✅ 最终答案

对以上答案 $K$ 取模 $2005$ 即可。

🧠复杂度分析

时间复杂度：$O(\log L)$（矩阵快速幂）

空间复杂度：$O(1)$（$3 \times 3$ 常量矩阵）

代码实现

#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <iomanip>
#include <ctime>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned int UI;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
const double PI = 3.14159265;
const double E = 2.71828182846;
const int mod = 2005;
const int look = 1000;
int fib[look] = {1, 2, 4, 6, 9, 15};

int main()
{
	ios::sync_with_stdio(false);
	int loop;
	for (int i=6; i<=look; i++)
	{
		fib[i] = (fib[i-1]+fib[i-3]+fib[i-4])%2005;
		if (fib[i] == 2 && fib[i-1] == 1)
		{
			loop = i-1;
			break;
		}
	}
	int L;
	while (cin >> L)
	{
		cout << fib[L%loop] << endl;
	}
	return 0;
}