题目分析

问题重述

我们需要计算所有长度为 $k$ 的二进制序列（海盗代码）的"值"之和。海盗代码的解析规则是：

• 将序列分割成尽可能多的部分，每个部分是一个有效的海盗表示
• 海盗表示：以连续两个1结尾的二进制序列，且满足特定的斐波那契加权和
• 代码的值是所有有效海盗表示对应的数字之和

关键观察

1. 海盗表示的特征：

   • 必须以"11"结尾
   • 前面的位不能有连续的1
   • 数值计算：$x = \sum_{i=0}^{a-2} s[i] \cdot \text{Fib}[2+i]$

2. 解析规则：贪心分割，从前往后尽可能多地分割出有效的海盗表示

3. 问题转化：我们需要计算所有长度为 $k$ 的二进制序列，按照上述规则解析后的数值之和

解法思路

方法：动态规划

步骤1：预处理斐波那契数

vector<long long> fib(2 * n + 10);
fib[1] = fib[2] = 1;
for (int i = 3; i <= 2 * n + 5; i++) {
    fib[i] = fib[i-1] + fib[i-2];
}

步骤2：定义DP状态

设：

• $dp[i]$：长度为 $i$ 的所有二进制序列的总值
• $cnt[i]$：长度为 $i$ 的有效海盗表示的数量
• $sum[i]$：长度为 $i$ 的所有有效海盗表示的数值之和

步骤3：状态转移

对于长度为 $i$ 的序列：

• 如果以"11"结尾，且前面没有连续1，则这是一个有效的海盗表示
• 否则，可以递归考虑更短的前缀

具体转移方程：

$$dp[i] = \sum_{j=1}^{i} (cnt[j] \cdot dp[i-j] + sum[j] \cdot ways[i-j]) $$

其中 $ways[i]$ 表示长度为 $i$ 的二进制序列数量。

代码实现

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
const int MAXN = 5005;

long long fib[MAXN * 2];
long long dp[MAXN], cnt[MAXN], sum[MAXN], ways[MAXN];

int main() {
    int n;
    cin >> n;
    
    // 预处理斐波那契数列
    fib[1] = fib[2] = 1;
    for (int i = 3; i <= 2 * n + 5; i++) {
        fib[i] = fib[i-1] + fib[i-2];
    }
    
    // 初始化
    ways[0] = 1;  // 空序列
    for (int i = 1; i <= n; i++) {
        ways[i] = (ways[i-1] * 2) % MOD;
    }
    
    // 计算cnt[i]和sum[i]：长度为i的有效海盗表示
    for (int len = 2; len <= n; len++) {
        // 有效的海盗表示必须以"11"结尾
        // 枚举前面len-2位的选择（不能有连续1）
        
        // 使用DP计算没有连续1的序列数量
        vector<long long> no_consecutive(len + 1);
        no_consecutive[0] = 1;
        no_consecutive[1] = 2;  // "0" or "1"
        
        for (int i = 2; i <= len - 2; i++) {
            // 以0结尾：no_consecutive[i-1]
            // 以1结尾：必须以0结尾的序列后面加1，即no_consecutive[i-2]
            no_consecutive[i] = (no_consecutive[i-1] + no_consecutive[i-2]) % MOD;
        }
        
        // 对于每个没有连续1的前缀，计算其数值
        // 这里需要更精细的计算
        
        // 简化：直接枚举所有有效模式
        for (int mask = 0; mask < (1 << (len - 2)); mask++) {
            // 检查是否有连续1
            bool valid = true;
            for (int i = 0; i < len - 3; i++) {
                if ((mask >> i & 1) && (mask >> (i + 1) & 1)) {
                    valid = false;
                    break;
                }
            }
            if (!valid) continue;
            
            // 计算这个海盗表示的数值
            long long value = 0;
            for (int i = 0; i < len - 2; i++) {
                if (mask >> i & 1) {
                    value += fib[2 + i];
                }
            }
            
            cnt[len] = (cnt[len] + 1) % MOD;
            sum[len] = (sum[len] + value) % MOD;
        }
    }
    
    // 特殊情况：长度为2的海盗表示只有"11"
    cnt[2] = 1;
    sum[2] = 1;  // 11_p = 1
    
    // 主DP：计算dp[i]
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = 0;
        for (int j = 2; j <= i; j++) {
            // 以长度为j的海盗表示开头
            if (cnt[j] > 0) {
                long long contribution = (sum[j] * ways[i