UVA 11125 Arrange Some Marbles 題解：狀態壓縮動態規劃處理顏色與長度約束

題目大意

有 n 種顏色彈珠，每種給定數量。排列成環，要求：

• 相同顏色連續段長度 ≤ 3。
• 相鄰段顏色不同且長度不同。
• 首尾段也視為相鄰，需滿足上述條件。

求合法排列總數。n ≤ 4，總數量 ≤ 3000。結果模給定 mod。

狀態壓縮 DP 設計

因顏色數固定為 4，每種顏色剩餘數量 ≤ 7（因段長 ≤ 3，實際最多 3），用 3 位存一種顏色剩餘量，4 種共 12 位，即八進制狀態 state（0..4095）。

DP 狀態：f[state][last_len][last_color][first_len][first_color] 表示剩餘狀態為 state，上一段長度 last_len、顏色 last_color，首段長度 first_len、顏色 first_color 時的方案數。

遞歸轉移

int dp(state, last_len, last_color) {
    if (state == 0) // 所有彈珠用完
        return (last_len != first_len && last_color != first_color) ? 1 : 0;
    if (memoized) return memo;
    ans = 0;
    解碼 state 得到各顏色剩餘數 rem[4];
    for (color = 0; color < 4; color++) if (color != last_color)
        for (len = 1; len <= min(3, rem[color]); len++) if (len != last_len)
            ans += dp(state - len * (1<<(3*color)), len, color);
    return memo = ans % mod;
}

初始化與答案

枚舉首段顏色 c 和長度 l，累加 dp(initial_state - l*(1<<(3*c)), l, c)。特殊情況：無彈珠時答案為 1。

複雜度

狀態數 8^4 = 4096，每狀態轉移 4 * 3 = 12，乘以首段枚舉 4*3=12，總計約 4096 * 144 ≈ 6e5，極快。

關鍵代碼 (C++)

int f[4500][5][5][5][5];
int num[5], N, PS, PC;
int dp(int state, int s, int c) {
    int &ans = f[state][PS][PC][s][c];
    if (ans != -1) return ans;
    if (!state) return ans = (PS != s && PC != c);
    int tmp[5], tS = state;
    for (int i = N-1; i >= 0; i--) {
        tmp[i] = tS / (1<<(3*i)); tS %= (1<<(3*i));
    }
    ans = 0;
    for (int i = 0; i < N; i++) if (i != c)
        for (int j = 1; j <= min(3, tmp[i]); j++) if (j != s)
            ans += dp(state - j*(1<<(3*i)), j, i);
    return ans %= mod;
}
void solve() {
    scanf("%d", &N);
    for (int i=0;i