BZOJ3841 ZCC Loves Intersection

2015.01.20 13:49 Tue| 2 visits oi_2015| 2015_刷题日常| Text

Problem

在 n 维坐标系上有 n 条分别平行于各坐标轴的线段,问存在两条直线相交的概率。

线段生成器的含义:

对于第 i 条直线,除第 i 维外两端点的坐标均为 [0, n-1] 内的随机整数。分别将这条线段左、右两端点的第 i 维坐标赋值为 [0, n-1] 内的随机整数,直到它在第 i 维上左端点坐标严格小于右端点坐标为止。

Solution

考虑分别平行于第 i、j 维坐标轴的两条直线 a、b 相交的概率。显然这两条线段若相交,其他维度上的坐标值都需要相同,其概率为 ${1\over n^{d-2}}$ 。

考虑在第 i 个维度上,两条直线可能相交仅当 $a1[i] \le b[i] \le a2[i]$ 。由于 $a1[i] < a2[i]$ ,有以下三种可能的情况。

  1. $a1[i] < b[i] < a2[i]$
  2. $a1[i] < b[i] = a2[i]$
  3. $a1[i] = b[i] < a2[i]$

当 b[i] 确定时,三种情况数分别为 $b[i]\times (n-b[i]-1)$、 $b[i]$、 $n-b[i]-1$ ,其中 b[i] 有 n 种可能的取值,而共有 $n{n\choose2}$ 种情况,因此满足符合条件的情况概率为

在第 j 个维度上同理。

分别平行于第 i、j 维坐标轴的两条直线 a、b 相交的概率为 ${1\over n^{d-2}}\times{(n+4)^2\over 9n^2}$ 。由于这两条直线共有 ${n\choose 2}$ 种选择方式,最终所得答案需要乘以 ${n(n-1)\over2}$ 。

Code

def gcd(a, b):
    if (b == 0):
        return a
    return gcd(b, a % b)

import sys
while 1:
    line = sys.stdin.readline()
    if not line:
        break
    n, d = line.split()
    n = int(n); d = int(d)
    p = d * (d - 1) * (n + 4) ** 2
    q = 18 * n ** d
    g = gcd(p, q)
    print "%d/%d" %(p / g, q / g)