在一组学生可以连续坐多少的方式,来自同一班级的学生必须交替

Question

有班级的M学生N,A[i]是来自的学生人数class_i,sum(A[i]) == M.所有这些学生将坐在一排M座位,同一班级没有2名学生坐在一起.

这些M学生可以连续坐多少个有效的方法？

例如,如果N = 2,A = {1,2},则输出应为2;

如果N = 2,A = {1,3},则输出应为0;

如果N = 3,A = {1,2,3},则输出应为120.

技术规格:N <47; A [i] <47; 总和(A)<447;

如果输出大于1000000007,则输出(结果%1000000007).

Answer 1

这个解决方案可能不是最佳的，但我认为这是一个好的开始。

这个问题有两个组成部分：

1. 将每个座位标记为类别（X 种方式）
2. 为学生分配座位（Y 种方式）

最终答案等于X*Y。

第 2 部分非常简单。Y = A(1)！A2）！...*一个）！

不过，计算第一部分很棘手。可以用DP来解决。复杂度 = N*A(1) A(2) ...*A(N) （这对我来说太贵了）

DP问题是：

F(a1,a2,..,an,last_letter=1) = F(a1-1,a2,..,an,last_letter!=1)+F(a1,a2-1,..,an,last_letter!=1)+F(a1,a2-1,..,an,last_letter! =1)+...+F(a1,a2,..,an-1,last_letter!=1)