BZOJ2729 [HNOI2012]排队

2015.01.13 09:54 Tue| 0 visits oi_2015| 2015_刷题日常| Text

Solution

简单递推,考虑将妹纸和老湿插入汉纸们排列的间隙中,可分为两种情况考虑:

  • 若两名老湿在同一间隙中 这两名老湿之间一定有一只妹纸 于是答案即为 汉纸的排列数 n! * (n + 1) 个老湿可能所在的空隙 * A(n + 2 个妹纸可以占据的间隙, m 个妹纸 - 1 个被夹在老湿们中间的可怜妹纸)。
  • 若两名老湿在不同间隙中 答案为 汉纸的排列数 n! * A(n + 1 个老湿可能所在的空隙, 2 个老湿) * A(n + 3 个老湿可以占据的间隙, m 个妹纸)

化简上述式子,易得最终答案。

Code

def mul(x, y):
    re = 1
    for i in range (x, y + 1):
        re = re * i
    return re

n, m = raw_input().split()
n = int(n); m = int(m)
print(mul(1, n + 1) * mul(n + 4 - m, n + 2) * (2 * m + n * (n + 3)))