5

有M来自N班级的学生，是来自,A[i]的学生人数。所有这些学生都会坐成一排，有座位，同一个班级没有两个学生并排坐。class_isum(A[i]) == MM

这些学生有多少种有效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）。

4

3 回答 3

0

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

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

  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,..,an-1,last_letter!=1)

于 2013-03-29T16:15:17.433 回答
0

首先请注意，给定输入列表的有效座位安排A使得，当新的大小类别到达sum(A)=n时，很容易计算有效座位安排的数量：m

  • m将新学生适合所有可能的n+1有效职位（有n老学生，这意味着n+1有效职位）。这就是组合的准确定义，C(n+1,m)这样的组合是有的。
  • 然后排列m新学生以获得所有可能的有效座位安排。

因此，新尺寸级别的到来使m有效座位安排的数量增加了C(n+1,m) * m!. 这建议使用以下算法（在 Python 中）：

import math
import scipy.misc

def f(A) :
    if len(A) == 2 :
        a,b = A
        if a == b  : 
        # two solutions o+o+ and +o+o without order consideration, then multiply by 2! * 2! to get all possible orders within classes
            return math.factorial(a) * math.factorial(b) * 2 
        elif abs( a - b ) == 1 : 
        # o+o+o without order consideration, then multiply by 2! * 3! to get all possible orders within classes
            return math.factorial(a) * math.factorial(b)
        else : # no solution
            return 0
    else : # the number of valid arrangement is multiplied by C(n+1,m) * m!
        return sum( f(A[:i]+A[i+1:]) * scipy.misc.comb( sum(A)-ai + 1, ai ) * math.factorial(ai) for i, ai in enumerate(A) )

让我们检查一下我们得到的结果是否与 OP 的示例相同：

f( [ 1,2 ] )
2

f( [ 1,3 ] )
0

f( [ 1, 2, 3 ] )
120.0

有用！让我们尝试三个 30 名学生的班级：

f( [ 30, 30, 30 ] )
2.6058794190003256e+115 # this is greater than the number of baryons in the universe!
于 2014-07-16T14:53:29.457 回答
0

考虑以下python代码：

import math

mem={}

def get_id(A, forbidden):
    count = {}
    for a in A:
        if a<>forbidden:
            n = A[a]
            count[n] = count.get(n,0)+1
    return frozenset( [A.get(forbidden, 0)] + count.items() )

def class_seatings(A, forbidden=None):
    if sum(A.values())==1:
        if forbidden in A:
            return 0
        else:
            return 1
    ssum = 0
    for a in A:
        if a <> forbidden:
            n = A[a]
            A2 = dict(A) 
            if n==1:
                del A2[a]
            else:
                A2[a] -= 1
            id = get_id(A2, a)
            if id not in mem:
                mem[id] = class_seatings(A2, a)
            cs = mem[id]
            ssum += cs
    return ssum

def student_seatings(A):
    assert all(map(lambda x: x>0, A.values()))
    facts = map(lambda x: math.factorial(x), A.values())
    mult = reduce(lambda x,y: x*y, facts, 1)
    return mult*class_seatings(A) % 1000000007

看起来它得到了正确的基本情况：

>>> student_seatings( {1:1, 2:2} )
2
>>> student_seatings( {1:1, 2:2, 3:3} )
120
>>> student_seatings( {1:1, 2:3} )
0
>>> student_seatings( {1:2, 2:2} )
8

mem但是，在您提到的要求之前，使用and的基本记忆方案get_id开始崩溃。要看到这一点，请观看进度

mem={}
for upper in range(2,11):
    A = dict( (x,x) for x in range(1,upper) )   
    print len(A), student_seatings(A)
    print len(mem)

产生

1 1
0
2 2
4
3 120
20
4 309312
83
5 579005048
329
6 462179000
1286
7 481882817
5004
8 678263090
19447
9 992777307
75581

有人关心改进它吗？

于 2013-08-06T00:54:49.053 回答