「SCOI 2008」着色方案

题目大意：有 $n$ 个木块排成一排，从左到右依次编号为 $1\cdots n$。你有 $k$ 种颜色的油漆，其中第 $i$ 种颜色的油漆足够涂 $c_i$ 个木块。所有油漆刚好足够涂满所有木块，即 $c_1+c_2+…+c_k=n$。统计任意两个相邻木块颜色不同的着色方案，输出方案数模 $1,000,000,007$ 的结果。$1 <= k <= 15, 1 <= c_i <= 5$

#1

设 $f[a][b][c][d][e][x]$ 表示目前还能涂 $1$ 次的颜色有 $a$ 个，能涂 $2$ 次的颜色有 $b$ 个……能涂 $5$ 次的有 $e$ 个，上一次用的是能涂 $x$ 次的颜色。

#include <cstdio>
#include <cstring>

const int P = 1000000007;
int a[6], f[16][16][16][16][16][6], k;

int dfs(int a, int b, int c, int d, int e, int x) {
    if (f[a][b][c][d][e][x] != -1) return f[a][b][c][d][e][x];
    if (!a && !b && !c && !d && !e) return 1;
    f[a][b][c][d][e][x] = 0;
    if (a) (f[a][b][c][d][e][x] += 1LL * (a - (x == 2)) * dfs(a - 1, b, c, d, e, 1) % P) %= P;
    if (b) (f[a][b][c][d][e][x] += 1LL * (b - (x == 3)) * dfs(a + 1, b - 1, c, d, e, 2) % P) %= P;
    if (c) (f[a][b][c][d][e][x] += 1LL * (c - (x == 4)) * dfs(a, b + 1, c - 1, d, e, 3) % P) %= P;
    if (d) (f[a][b][c][d][e][x] += 1LL * (d - (x == 5)) * dfs(a, b, c + 1, d - 1, e, 4) % P) %= P;
    if (e) (f[a][b][c][d][e][x] += 1LL * e * dfs(a, b, c, d + 1, e - 1, 5) % P) %= P;
    return f[a][b][c][d][e][x];
}

int main() {
    scanf("%d", &k);
    for (int i = 1; i <= k; ++i) {
        int x; scanf("%d", &x); ++a[x];
    }
    memset(f, -1, sizeof f);
    printf("%d\n", dfs(a[1], a[2], a[3], a[4], a[5], 0));
    return 0;
}

时间复杂度 $O(k^5c)$

#2

设 $f[i][j]$ 表示前 $i$ 种颜色全用完，有 $j$ 对相邻的同色块的方案数。

考虑将 $c[i+1]$ 分成 $a$ 组的插入到已经弄好的块中，其中 $b$ 组插入到之前同色的之间，$a-b$ 组插空放不相邻，有状态转移方程（其中 $sum[i]=\sum\limits_{k=1}^{i}c_k$）

$$f[i + 1][j - b + c_{i+1}-a] += f[i][j] \binom{c_{i+1}-1}{a-1} \binom{j}{b} \binom{sum[i]-j+1}{a-b}$$

其中 $j-b+c_{i+1}-a$ 的意思是，到第 $i+1$ 个颜色，把这个颜色分成 $a$ 组后，产生了 $c_{i+1}-a$ 对相邻的同色块（组与组之间互不相邻），$b$ 组插入到之前同色的之间，就减少了 $b$ 对同色块。

#include <cstdio>

const int N = 106, P = 1e9+7;

int C[N][N], f[N][N], c[N], sum[N], k;

void get_c() {
    C[0][0] = 1;
    for (int i = 1; i <= 75; ++i) {
        C[i][0] = 1;
        for (int j = 1; j <= i; ++j)
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % P;
    }
}

int main() {
    scanf("%d", &k);
    for (int i = 1; i <= k; ++i) {
        scanf("%d", &c[i]);
        sum[i] = sum[i-1] + c[i];
    }
    get_c();
    f[1][c[1]-1] = 1; //a[1]-1是最多对数
    for (int i = 1; i < k; ++i)
        for (int j = 0; j < sum[i]; ++j) {
            if (!f[i][j]) continue;
            for (int a = 1; a <= c[i+1]; ++a)
                for (int b = 0; b <= a && b <= j; ++b)
                    (f[i+1][j+c[i+1]-a-b] += 1LL * f[i][j] * C[c[i+1]-1][a-1] % P * C[j][b] % P * C[sum[i]-j+1][a-b] % P) %= P;
        }
    printf("%d\n", f[k][0]);
    return 0;
}

时间复杂度 $O(k^2c^3)$