#P3841. ZCC Loves Intersection

    ID: 3045 传统题 1000ms 128MiB 尝试: 37 已通过: 29 难度: 6 上传者: 标签>CF1900提高期望线性性欧几里得算法有理数精确运算高精度乘法By镇海中学

ZCC Loves Intersection

题目描述

在一个 DD 维直角坐标系中,每个坐标轴各对应一条与该轴平行的线段,共 DD 条。每秒,每条线段都独立重新生成。对于平行于第 ii 轴的线段,生成过程如下。

  1. 对每个维度 j≠ij\ne i,从整数集合 {0,1,…,N−1}\{0,1,\dots,N-1\} 中独立均匀选取一个坐标。线段两个端点在该维度共用这个坐标。
  2. 在第 ii 维独立均匀生成两个端点坐标。若第一个坐标大于等于第二个坐标,就重新抽取这两个坐标,直到第一个严格小于第二个。其他维度的坐标保持不变。

每对有公共点的线段每秒产生一个单位能量。相交包含只在端点相接。求每秒能量的期望值。

输入格式

输入包含多组数据,读到文件结尾为止,至多 1010 组。每组一行两个整数 N,DN,D,满足 2≤N≤1092\le N\le10^9,1≤D≤991\le D\le99。

输出格式

每组输出一行。若答案是整数,直接输出该整数,否则以 p/q 形式输出最简分数。

样例

2 2
3 3
5 5
1
49/81
18/625

原 BZOJ 题面存档及随机过程伪代码