自动搬运

查看原文

来自洛谷，原作者为

	Cyhlnj **

搬运于2025-08-24 21:38:08，当前版本为作者最后更新于2018-01-26 10:27:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

还有更优秀的组合数学+$DP$的做法

$sum[i]$表示$c[i]$的前缀和，$C[i][j]$即$C_{i}^{j}$，大小写区分开

设$f[i][j]$表示用了前$i$种颜色涂了$sum[i]$个块，其中有$j$对相邻同色块的方案数

考虑转移$f[i][j]$

$c[i + 1]$分成$a$组的插入到已经弄好的块中

$b$组插入到之前同色的之间

$a-b$组插空放不相邻

那么就是转移给$f[i + 1][j - b + c[i + 1] - a]$

方案数为$f[i][j] * C[c[i + 1] - 1][a - 1] * C[j][b] * C[sum[i] + 1 - j][a - b]$

$C[c[i + 1] - 1][a - 1]$就是分成$a$组的方案数（无序的）

$C[j][b]$就是插入到之前同色的之间的方案数（位置不同）

$C[sum[i] + 1 - j][a - b]$就是相当于前面有$sum[i]+1$个位置，$j$个相邻块占据的位置不能放，$a-b$插入进去的方案数

# include <bits/stdc++.h>
# define RG register
# define IL inline
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
const int Zsy(1e9 + 7);

IL ll Input(){
    RG ll x = 0, z = 1; RG char c = getchar();
    for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
    for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
    return x * z;
}

int k, c[16], C[80][80], f[20][80], sum[16];

IL void Prepare(){
    C[0][0] = 1;
    for(RG int i = 1; i <= 75; ++i){
        C[i][0] = 1;
        for(RG int j = 1; j <= 75; ++j)
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % Zsy;
    }
}

int main(RG int argc, RG char* argv[]){
    Prepare();
    k = Input();
    for(RG int i = 1; i <= k; ++i) c[i] = Input(), sum[i] = sum[i - 1] + c[i];
    f[1][c[1] - 1] = 1;
    for(RG int i = 1; i < k; ++i)
        for(RG int j = 0; j < sum[i]; ++j){
            if(!f[i][j]) continue;
            for(RG int a = 1; a <= c[i + 1]; ++a)
                for(RG int b = 0; b <= a && b <= j; ++b){
                    RG int ret = 1LL * f[i][j] * C[c[i + 1] - 1][a - 1] % Zsy * C[j][b] % Zsy;
                    ret = 1LL * ret * C[sum[i] + 1 - j][a - b] % Zsy;
                    (f[i + 1][j + c[i + 1] - a - b] += ret) %= Zsy;
                }
        }
    printf("%d\n", f[k][0]);
    return 0;
}