1. 至少有 3 種不同數字出現。
2. 至少存在一對相鄰位置差值為 3（即出現 1 和 4 相鄰）。

求合法序列總數。多組輸入，-1 結束。

狀態定義

dfs(pos, used_mask, has_diff3, last) 返回從位置 pos 開始填寫，已用數字集合 used_mask（4 位掩碼），是否已有差值 3 相鄰對 has_diff3，上一位值 last 的合法方案數。

遞推邏輯

long long dfs(int pos, int mask, int has3, int last) {
    if (pos == n) 
        return (__builtin_popcount(mask) >= 3 && has3) ? 1 : 0;
    
    if (dp[pos][mask][has3][last] != -1) 
        return dp[pos][mask][has3][last];
    
    long long ans = 0;
    for (int cur = 1; cur <= 4; ++cur) {
        int nmask = mask | (1 << (cur-1));
        int nhas3 = has3 || (abs(cur - last) == 3);
        ans += dfs(pos+1, nmask, nhas3, cur);
    }
    return dp[pos][mask][has3][last] = ans;
}

優化技巧

1. 狀態壓縮：mask 用 4 位表示 {1,2,3,4} 是否出現，has3 0/1，last 0~4（0 表示無前驅）。總狀態 17 × 16 × 2 × 5 = 2720，極小。
2. 記憶化數組：dp[20][16][2][5] 初始化 -1，long long 存儲結果（n=16 時答案 < 4^16 ≈ 4e9，fit in 64bit）。
3. 初始調用：dfs(0, 0, 0, 0)。

完整代碼

#include <cstdio>
#include <cstring>
#define ll long long
ll dp[20][16][2][5];
int n;

ll dfs(int pos, int mask, int has3, int last) {
    if (pos == n) 
        return (__builtin_popcount(mask) >= 3 && has3) ? 1 : 0;
    if (dp[pos][mask][has3][last] != -1) 
        return dp[pos][mask][has3][last];
    ll ans = 0;
    for (int cur = 1; cur <= 4; ++cur) {
        int nmask = mask | (1 << (cur-1));
        int nhas3 = has3 || ( (cur==1 && last==4) || (cur==4 && last==1) );
        ans += dfs(pos+1, nmask, nhas3, cur);
    }
    return dp[pos][mask][has3][last] = ans;
}

int main() {
    while (scanf("%d", &n) == 1 && n != -1) {
        memset(dp, -1, sizeof(dp));
        printf("%d: %lld\n", n, dfs(0, 0, 0, 0));
    }
    return 0;
}

複雜度

• 時間：O(n × 16 × 2 × 5 × 4) ≈ O(n)，n≤16 瞬間出結果。
• 空間：O(n × 16 × 2 × 5) ≈ 2720 × 8 bytes ≈ 22KB。

舉一反三

此類「序列計數 + 全局約束（種類數、相鄰關係）」問題，通用模板：

1. 位置 pos 遞推。
2. 掩碼記錄「已用元素集合」。
3. 布爾標記記錄「是否滿足特定全局條件」。
4. 必要時攜帶 last 處理相鄰約束。
5. 記憶化搜索自動去重重疊子問題。