P3330 [ZJOI2011] 看电影

题目描述

到了难得的假期，小白班上组织大家去看电影。但由于假期里看电影的人太多，很难做到让全班看上同一场电影。最后大家在一个偏僻的小胡同里找到了一家电影院，但这家电影院分配座位的方式很特殊，具体方式如下：

电影院的座位共有 $K$ 个，并被标号为 $1 \sim K$。每个人买完票后会被随机指定一个座位，具体来说是从 $1 \sim K$ 中等概率随机选取一个正整数，设其为 $L$。

如果编号 $L$ 的座位是空位，则这个座位就分配给此人，否则将 $L$ 加一，继续前面的步骤；如果不存在编号 $L$ 的座位，则该人只能站着看电影，即所谓的站票。

小白班上共有 $N$ 人（包括小白自己），作为数学爱好者，小白想知道全班都能够有座位的概率是多少。

本题有多组数据。第一行一个整数 $T$ 表示数据组数，接下来 $T$ 行每行两个整数 $N,K$ 表示人数和电影院座位数。

对于每一组数据数据输出一行两个整数 $A,B$，表示答案为 $\frac{A}{B}$。你需要保证 $\gcd(A,B) = 1$。

1
2
3

1 1
0 1
3 4

对于 $100 %$ 的数据，$1 \leq T \leq 50$，$1 \leq N,K \leq 200$。

本题所问的概率，本质上是合法的指定座位方案数除以总情况数。其中总情况数显然是 $k^n$，只要求出符合限制的指定座位方案数即可。

首先，如果人数多于座位数，即 $n > k$，是绝对无法达成“都有座位”的，直接特判输出。

如果座位总数够坐，即 $n \ge k$，我们不妨虚构出来一个从座位 $k$ 到座位 1 的传送门，如果一个人他走到座位 $k$ 还没有空位置的话，他就可以走到第一个座位，再依次向后找到一个空座位。由于这样构成了一个环，座位的个数一定是够坐的。这样每个人都有座位了。

按照电影院的特殊限制，我们要求的就是没有人穿过传送门的方案数。我们不妨再虚构一个座位 $k+1$，现在如果有人走到 $k$ 没有座位，就会先坐在 $k+1$，那么一个方案不合法当且仅当 $k+1$ 位置被人坐了，一个方案合法当且仅当 $k+1$ 位置没有人坐。

将 $n$ 个人在长度为 $k+1$ 圆环上指定座位的方案数为 $\frac{(k+1)^n}{k+1} = (k+1)^{n-1}$。所有人坐完之后，有 $k-n+1$ 个位置是空的。我们可以选择从这些位置断环成链，并把这些位置当做 $k+1$ 号座位，于是得到了一个合法方案。

于是答案就是 $$ \frac{(k+1)^{n-1}(k-n+1)}{k^n} $$ 显然 $(k+1)^{n-1}$ 和 $k^n$ 互质，因此只要考虑 $k-n+1$ 和 $k^n$ 的 gcd。需要使用高精度和快速幂。