逃离地球的博客

着色方案题解

2021-02-22 · 10 min read

题目链接

题意

$n$ 个小球， $m$ 种颜色，第 $i$ 种颜色有 $c_i$ 个，保证 $\sum c_i=n$ ，问有多少种染色方案，使得任意两个相邻小球颜色不同。

题解

这道题有多种方法，都具有一定的启发性，故在这里一并给出。

算法一：暴力 dp

从左到右依次确定每个小球的颜色，直接在状态中表示每个颜色剩余的数量与最后一个小球的颜色，直接转移即可。

时间复杂度 $\mathcal O({c_i}^{m}\times m)$ ，无法接受。

算法二：优化状态设计

发现 $c_i$ 的范围较小，且剩余个数相同的小球对我们来说没有区别，于是在状态中只需记录每种剩余数量的颜色有多少个，与最后一个小球的颜色的剩余数量即可，转移同样比较显然，在此不再赘述。

时间复杂度 $\mathcal O({m}^{c_i}\times c_i)$ ，使用记忆化搜索实现，可以通过此题。

算法三：改变枚举方式

与此题类似（另外吐槽一下，这题咋是黄题啊，本菜鸡觉得挺难的啊……），考虑改变枚举方式，枚举颜色而非枚举小球，并且认为是不断地向小球序列中插入一种新颜色的小球。这样带来的好处是单次插入的小球颜色全部相同，方便统计插入后有多少相邻的同颜色小球。

于是设 $f_{i,j}$ 表示枚举到第 $i$ 个颜色，当前小球序列中有 $j$ 对相邻的同颜色小球的方案数，则答案为 $f_{n,0}$ 。设 $s_i=\sum_{j=1}^i c_j$ 。

考虑在 $f_{i-1,j}$ 的基础上插入第 $i$ 种颜色的小球，设这 $c_i$ 个小球被原来的序列分成了 $a$ 段，且其中 $b$ 段隔开了原来相邻的一对同颜色小球，则有 $a\le\min(s_{i-1}+1,c_i),b\le\min(a,j)$ 。且插入这些小球后，相邻同颜色小球的个数变为 $j-b+c_i-a$ 。

再考虑统计方案数，先插板法分段，再选出这 $a$ 段和 $b$ 段，方案数为 $\dbinom{c_i-1}{a-1}\times\dbinom{s_{i-1}+1-j}{a-b}\times\dbinom{j}{b}$ 。

于是可以写出转移方程式：

f_{i,j-b+c_i-a}=\sum_{j=0}^{s_{i-1}-1}\sum_{a=1}^{\min(s_{i-1}+1,c_i)}\sum_{b=0}^{\min(a,j)}f_{i-1,j}\times\binom{c_i-1}{a-1}\times\binom{s_{i-1}+1-j}{a-b}\times\binom{j}{b}

时间复杂度 $\mathcal O(n^4)$ 。

算法四：更加优秀的容斥做法

设 $f_i$ 表示钦定 $i$ 个球与左边的球同色的方案数， $g_i$ 表示恰好 $i$ 个球与左边的球同色的方案数，则答案为 $g_0$ 。根据二项式反演，有 $g_0=\sum_{i=0}^n(-1)^if_i$ 。

现在考虑如何求出 $f_k$ 。

设颜色 $1$ ，颜色 $2$ ，……，颜色 $m$ 分别有 $k_1,k_2\cdots k_m$ 个球与左边的球同色（ $\sum k_i=k$ ）。考虑颜色 $i$ 的小球，在序列中被分成了 $c_i-k_i$ 段连续的子段，共有 $\dbinom{c_i-1}{k_i}$ 种分段方法。再考虑整个序列，发现就是这 $n-k$ 个颜色段的可重排列问题（每种颜色内部的顺序不能改变，因为在枚举分段方法时已经枚举到了）。

于是有：

f_k=\sum_{k_1+k_2+\cdots+k_m=k}\binom{c_1-1}{k_1}\binom{c_2-1}{k_2}\cdots\binom{c_m-1}{k_m}\frac{(n-k)!}{(c_1-k_1)!(c_2-k_2)!\cdots(c_m-k_m)!}

发现这个式子其实是卷积的形式，使用暴力卷积（其实就是背包）可以以 $\mathcal O(n^3)$ 的复杂度求出 $f_{1\sim n}$ 。

似乎可以用某些类似分治的卷积顺序，在不使用 fft 的情况下将复杂度优化致 $\mathcal O(n^2\log n)$ 。

算法五：使用 `fft` 优化

再推一推上面这个式子，答案其实就是这个：

\sum_{k=0}^n(-1)^k(n-k)![x^k]\prod_{i=1}^m\sum_{j=0}^{c_i-1}\binom{c_i-1}{j}\frac{x^j}{(c_i-j)!}

使用 fft 求多项式卷积，时间复杂度 $\mathcal O(n\log^2n)$ 。

~~其实我不会写 fft~~

代码

算法一、算法二略。

算法三：

#include <bits/stdc++.h>
using namespace std;
#define int long long
int read() {
    int ret = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) f = (ch == '-') ? -f : f, ch = getchar();
    while (isdigit(ch)) ret = ret * 10 + ch - '0', ch = getchar();
    return ret * f;
}

const int P = 1e9 + 7, N = 1000;
int n, col[N], sum[N], f[N][N], c[N][N];

signed main() {
    n = read();
    for (int i = 1; i <= n; ++i) col[i] = read(), sum[i] = sum[i - 1] + col[i];

    c[0][0] = 1;
    for (int i = 1; i <= 100; ++i) {
        c[i][0] = 1;
        for (int j = 1; j <= 100; ++j)
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % P;
    }

    f[1][col[1] - 1] = 1;
    for (int i = 1; i < n; ++i)
        for (int j = 0; j <= sum[i] - 1; ++j)
            for (int a = 1; a <= min(sum[i] + 1, col[i + 1]); ++a)
                for (int b = 0; b <= min(j, a); ++b)
                    f[i + 1][j + col[i + 1] - a - b] +=
                        f[i][j] * c[sum[i] + 1 - j][a - b] % P * c[j][b] % P *
                        c[col[i + 1] - 1][a - 1] % P,
                        f[i + 1][j + col[i + 1] - a - b] %= P;

    printf("%lld\n", f[n][0]);
    return 0;
}

算法四：

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

typedef long long ll;
const int MAXN = 105, MOD = 1e9 + 7;
inline void ADD(int& x, int y) {
    x += y;
    if (x >= MOD) x -= MOD;
}
inline void DEC(int& x, int y) {
    x -= y;
    if (x < 0) x += MOD;
}
ll q_pow(ll a, ll b, ll p = MOD) {
    ll ret = 1;
    for (; b; a = a * a % p, b >>= 1)
        if (b & 1) ret = ret * a % p;
    return ret;
}
ll q_inv(ll x, ll p = MOD) { return q_pow(x, p - 2, p); }

int N, M, ans, c[MAXN], f[MAXN], g[MAXN], fac[MAXN], ifac[MAXN];
inline int C(int n, int m) {
    return 1ll * fac[n] * ifac[m] % MOD * ifac[n - m] % MOD;
}

int main() {
    scanf("%d", &M);
    for (int i = 1; i <= M; ++i) scanf("%d", &c[i]), N += c[i];
    fac[0] = 1;
    for (int i = 1; i <= N; ++i) fac[i] = 1ll * fac[i - 1] * i % MOD;
    ifac[N] = q_inv(fac[N]);
    for (int i = N - 1; i >= 0; --i)
        ifac[i] = 1ll * ifac[i + 1] * (i + 1) % MOD;
    f[0] = 1;
    for (int i = 1; i <= M; ++i) {
        for (int j = 0; j <= N; ++j) g[j] = 0;
        for (int j = 0; j <= N; ++j)
            if (f[j]) {
                for (int k = 0; k < c[i]; ++k)
                    ADD(g[j + k], 1ll * f[j] * C(c[i] - 1, k) % MOD *
                                      ifac[c[i] - k] % MOD);
            }
        for (int j = 0; j <= N; ++j) f[j] = g[j];
    }
    for (int i = 0; i <= N; ++i) {
        int tmp = 1ll * fac[N - i] * f[i] % MOD;
        if (i & 1)
            DEC(ans, tmp);
        else
            ADD(ans, tmp);
    }
    printf("%d", ans);
    return 0;
}

算法五：不会写 fft，以后再说……

感谢神仙 Mr_Wu 对本篇题解做出的巨大贡献！！！

着色方案 题解

题意

题解