核心分析

1. 问题本质：统计长度为 ( n )、元素取自集合 ( A ) 的序列中，满足“任意相同元素间距 ≥ 其自身值”的序列数量，结果对 $( 10^9 + 7 )$ 取模。
2. 关键约束：集合 ( A ) 元素 ≤ 8，且 $( n ≤ 100 )$，适合用动态规划记录最近出现位置的状态。
3. 状态设计：用 DP 数组记录“序列长度为 ( i ) 时，各元素最近出现位置的状态”对应的序列数。由于元素最多 8 个，且只需关注“最近一次出现是否在禁忌区间内”，可压缩状态。

状态定义

• 定义 $( dp[i][mask] )$：长度为 ( i ) 的序列，最近一次各元素出现位置的状态为 ( mask ) 时的美丽序列数量。
• ( mask ) 是长度为 ( m ) 的二进制状态（$( m ≤ 8 )$），第 ( k ) 位表示集合 ( A ) 中第 ( k ) 个元素：
  • 若为 ( 0 )：该元素未使用过，或最近一次使用位置距离当前位置 ≥ 其自身值（可再次使用）。
  • 若为 ( 1 )：该元素最近一次使用位置距离当前位置 < 其自身值（不可再次使用）。

转移逻辑

1. 初始化：$( dp[0][0] = 1 )$（空序列，状态为 0，数量为 1）。
2. 状态转移：
   • 对于每个长度 ( i )（从 ( 0 ) 到 ( n-1 )），遍历所有可能状态 ( mask )。
   • 对于集合 ( A ) 中的每个元素 ( x )（对应索引 ( k )）：
     • 若 ( mask ) 的第 ( k ) 位为 ( 0 )（可使用 ( x )）：
       • 计算新状态 $( new\_mask )$：
         • 先将原 ( mask ) 所有位右移 1 位（距离当前位置+1，禁忌区间缩小）。
         • 若 $( x > 1 )$：新状态第 ( k ) 位置为 ( 1 )（使用后，未来 ( x-1 ) 个位置不可再用）；若 ( x = 1 )：第 ( k ) 位仍为 ( 0 )（1 的间距要求为 1，下次可直接使用）。
       • 转移方程：$( dp[i+1][new\_mask] = (dp[i+1][new\_mask] + dp[i][mask]) \mod (10^9 + 7) )$。
3. 最终结果：遍历 $( dp[n][mask] )$ 所有可能状态，求和即为答案。

复杂度分析

• 时间复杂度：$( O(n \times 2^m \times m) )$。$( n ≤ 100 )$，$( m ≤ 8 )$，$( 2^8 = 256 )$，总运算量约 $( 100 \times 256 \times 8 = 204800 )$，效率极高。
• 空间复杂度：$( O(n \times 2^m) )$，可优化为 $( O(2^m) )$（仅保留前一长度的状态）。

代码实现

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MOD = 1e9 + 7;
const int MAX_N = 105;
const int MAX_MASK = 1 << 8; // 2^8 = 256

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> A(m);
    for (int i = 0; i < m; ++i) {
        cin >> A[i];
    }

    // dp[i][mask]: 长度为i，状态为mask的序列数
    int dp[MAX_N][MAX_MASK];
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;

    for (int i = 0; i < n; ++i) { // 当前长度为i，构造长度为i+1
        for (int mask = 0; mask < (1 << m); ++mask) { // 遍历所有状态
            if (dp[i][mask] == 0) continue;
            for (int k = 0; k < m; ++k) { // 尝试选择第k个元素
                int x = A[k];
                if (mask & (1 << k)) continue; // 该元素处于禁忌状态，不可选

                // 计算新状态
                int new_mask = mask >> 1; // 所有元素距离+1，禁忌状态右移
                if (x > 1) {
                    new_mask |= (1 << (k - 1)); // x>1时，新状态第k-1位设为1（下次需间隔x-1）
                }
                // 若x=1，new_mask保持mask>>1（第k位为0，下次可直接选）

                dp[i+1][new_mask] = (dp[i+1][new_mask] + dp[i][mask]) % MOD;
            }
        }
    }

    // 求和所有长度为n的状态
    int ans = 0;
    for (int mask = 0; mask < (1 << m); ++mask) {
        ans = (ans + dp[n][mask]) % MOD;
    }
    cout << ans << endl;

    return 0;
}

算法标签

• 动态规划（DP）
• 状态压缩
• 计数问题
• 模运算

关键细节

1. 状态压缩合理性：$( m ≤ 8 )$ 导致状态数仅 256，极大降低时间复杂度。
2. 禁忌状态处理：右移操作巧妙模拟“距离增加”，避免记录具体位置，仅关注“是否在禁忌区间”。
3. 模运算规范：每步转移都取模，防止数值溢出（序列数可能极大）。
4. 1 的特殊处理：由于 1 的间距要求为 1，使用后下次仍可直接选，无需设置禁忌位。