Hdu 4532 湫秋系列故事——安排座位

Posted on | Views:

容斥原理 + 多项式卷积.

经典模型,有 $n$ 种颜色的球,每种球有 $a_i$ 个,要将它们排成一行,使得相邻两个球颜色不同,求方案数.

下面认为同种颜色的球是没有区别的,若有区别,最后将答案乘上 $\prod (a_i!)$ 即可.

用容斥原理计算,若恰有 $k$ 个位置是相邻两个球颜色相同的,方案数为 $t(k)$ ,则对答案贡献为 $(-1)^k t(k)$ .

考虑每种颜色的小球贡献,若第 $i$ 种球在最后有 $j$ 个位置是相邻的,那么实际对可重排列长度的贡献个数为 $a_i-j$ ,那么可重排列的分子的贡献放在最后计算,分母的贡献和容斥系数拆到每种球上,将每种球的多项式卷起来就可以了.

具体地,对于第 $i$ 种球,我们构造一个多项式
$$
f(i)=\sum_{j=0}^{a_i-1} (-1)^j\binom {a_i-1}j \frac{1}{(a_i-j)!}x^{a_i-j}
$$
其中 $\binom{a_i-1}{j}$ 表示选择哪 $j​$ 个位置合并在一起.

记 $F=\prod f(i), m=\sum a_i$ ,答案即为 $\sum_{i=n}^{m} i!\cdot [x^i]F​$ .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
void print(int x)
{
	if (x >= 10)
		print(x / 10);
	putchar('0' + x % 10);
}
void write(int x, char c)
{
	if (x < 0)
		putchar('-'), x = -x;
	print(x);
	putchar(c);
}
const int P = 1e9 + 7;
int add(int a, int b)
{
	return a + b >= P ? a + b - P : a + b;
}
void inc(int &a, int b)
{
	a = add(a, b);
}
int mul(int a, int b)
{
	return 1LL * a * b % P;
}
int fpow(int a, int b)
{
	int res = 1;
	while (b)
	{
		if (b & 1)
			res = mul(res, a);
		a = mul(a, a);
		b >>= 1;
	}
	return res;
}
const int N = 500 + 10;
int fac[N], invfac[N], binom[N][N];
void init(int mx)
{
	fac[0] = invfac[0] = binom[0][0] = 1;
	for (int i = 1; i <= mx; ++i)
	{
		binom[i][0] = 1;
		for (int j = 1; j <= i; ++j)
			binom[i][j] = add(binom[i - 1][j - 1], binom[i - 1][j]);
		fac[i] = mul(fac[i - 1], i);
		invfac[i] = fpow(fac[i], P - 2);
	}
}
int n, m, a, poly[N], coef[N];
int solve()
{
	int ans = 0, prod = 1;	
	n = read(), m = 0;
	poly[0] = 1;
	for (int t = 1; t <= n; ++t)
	{
		int a = read();
		for (int j = 0; j < a; ++j)
		{
			coef[a - j] = mul(binom[a - 1][j], invfac[a - j]);
			if (j & 1)
				coef[a - j] = add(P, -coef[a - j]);
		}
		m += a, prod = mul(prod, fac[a]);
		for (int i = m; i >= 0; --i)
		{
			poly[i] = 0;
			for (int j = 1; j <= a && j <= i; ++j)
				inc(poly[i], mul(coef[j], poly[i - j]));
		}
	}	
	for (int i = n; i <= m; ++i)
		inc(ans, mul(fac[i], poly[i]));
	ans = mul(ans, prod);
	for (int i = 0; i <= m; ++i)
		poly[i] = 0;
	return ans;
}
int main()
{
	init(500);
	int cases = read();
	for (int i = 1; i <= cases; ++i)
	{
		int ans = solve();
		printf("Case %d: %d\n", i, ans);
	}
	return 0;
}