时间限制：C/C++ 5秒，其他语言10秒
空间限制：C/C++ 65536K，其他语言131072K
64bit IO Format: %lld
题目描述
有
n
n
n个木块，从左到右排成一排，你有k种颜色，每种颜色的可以涂
c
i
c_i
ci?个木块，所有的颜色正好够涂所有的木块，即
c
1
+
c
2
+
.
.
.
+
c
k
=
n
c_1+c_2+...+c_k=n
c1?+c2?+...+ck?=n。涂色时要求任意两块相邻木块不能同色，请统计出不同着色方案的总数。两种着色方案是不同的当且仅当两种方案至少有一个位置的木块颜色是不同的。
输入描述:
第一行输入一个
T
T
T，表示数据组数，每组数据的第一行一个正整数
k
(
1
≤
k
≤
30
)
k(1\le k\le30)
k(1≤k≤30)表示颜色种数，第二行
k
k
k个整数
c
1
,
c
2
,
.
.
.
,
c
k
(
1
≤
c
i
≤
30
)
c_1,c_2,...,c_k(1\le c_i\le30)
c1?,c2?,...,ck?(1≤ci?≤30)，表示每种颜色可涂的木块数。
输出描述:
输出
T
T
T行，表示每一组的方案数模1,000,000,007的结果。
示例
输入
2
3
1 2 3
6
6 6 6 6 6 6
输出
10
466309087
思路：
d
[
i
]
[
j
]
d[i][j]
d[i][j]表示全部使用完前
i
i
i种颜色后，还有
j
j
j对相邻且颜色相同的木块的方案数，那么答案即为
d
[
n
]
[
0
]
d[n][0]
d[n][0]。考虑转移，如何将当前第
i
i
i种颜色全部插入。
设前
i
?
1
i-1
i?1种颜色数量和为
S
i
?
1
S_{i-1}
Si?1?，且总共有
j
j
j对相邻且颜色相同的木块。将第
i
i
i种颜色分为连续的
k
k
k段(方案数有
C
c
i
?
1
k
?
1
)
C_{c_i-1}^{k-1})
Cci??1k?1?)，并将其中
h
(
h
≤
k
,
h
≤
j
)
h(h\le k,h\le j)
h(h≤k,h≤j)段插入
j
j
j对相邻且颜色相同的木块中间（有
C
j
h
C_j^h
Cjh?种），其余的插入其他位置(有
C
1
+
S
i
?
1
?
j
k
?
h
C_{1+S_{i-1}-j}^{k-h}
C1+Si?1??jk?h?种)，那么新的相邻且颜色相同的木块对数为
c
i
?
1
?
(
k
?
1
)
+
j
?
h
c_i-1-(k-1)+j-h
ci??1?(k?1)+j?h，所以转移为
d
[
i
]
[
c
i
?
k
+
j
?
h
]
=
∑
d
[
i
?
1
]
[
j
]
?
C
c
i
?
1
k
?
1
?
C
j
h
?
C
1
+
S
i
?
1
?
j
k
?
h
d[i][c_i-k+j-h]=\sum d[i-1][j]*C_{c_i-1}^{k-1}*C_j^h*C_{1+S_{i-1}-j}^{k-h}
d[i][ci??k+j?h]=∑d[i?1][j]?Cci??1k?1??Cjh??C1+Si?1??jk?h?
复杂度 O ( c i 2 ? S n ? n ) O(c_i^2*S_n*n) O(ci2??Sn??n)。
#include<bits/stdc++.h>
#define lson (k<<1)
#define rson (k<<1)+1
#define mid (l+r)/2
#define sz(x) int(x.size())
#define pii pair<ll,ll>
using namespace std;
const int MAX=910;
const int MOD=1e9+7;
const double PI=acos(-1.0);
typedef long long ll;
ll d[31][MAX],a[31],c[MAX][MAX];
int solve()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)a[i]+=a[i-1];
memset(d,0,sizeof d);
for(int i=1;i<=n;i++)
{
int m=a[i]-a[i-1];
if(i==1)d[i][m-1]=1;
else
{
for(int j=0;j<a[i-1];j++)
for(int k=1;k<=m;k++)
for(int h=0;h<=min(k,j);h++)
{
d[i][m-k+j-h]+=d[i-1][j]*c[m-1][k-1]%MOD*c[j][h]%MOD*c[a[i-1]+1-j][k-h]%MOD;
d[i][m-k+j-h]%=MOD;
}
}
}
printf("%lld\n",d[n][0]);
}
int main()
{
c[0][0]=1;
for(int i=1;i<=900;i++)
{
c[i][0]=1;
for(int j=1;j<=i;j++)c[i][j]=(c[i-1][j-1]+c[i-1][j])%MOD;
}
int T;
cin>>T;
while(T--)solve();
return 0;
}
