[JZOJ4745]看电影

Problem

听说NOIP2016大家都考得不错,于是CCF奖励省常中了\( K \)张变形金刚5的电影票奖励OI队的同学去看电影。可是省常中OI队的同学们共有\( N(N \geq K)\)人。于是机智的你想到了一个公平公正的方法决定哪\(K\)人去看电影。
\(N\)个人排成一圈,按顺时针顺序标号为\(1 \text{~} N\),每次随机一个还存活的人的编号,将这个人踢出。继续上述操作,直到剩下\(K\)个人。
但这样显然太无聊了,于是小S又想出一个牛逼的方法。
\(N\)个人排成一圈,按顺时针顺序标号为\(1 \text{~} N\),每次随机一个\(1 \text{~} N\)的编号,假设随机到的编号是\(X\),如果编号为\(X\)的人还未踢出,则将这个人踢出,否则看编号为\(X \mod N + 1\)(即顺时针顺序下一个编号)的人是否存活,如果还未踢出则将他踢出,否则继续看编号\((X + 1) \mod  N +1\)的人,如果已被踢出看顺时针的下一个…………,以此类推,直到踢出一个人为止。重复上述操作,直到剩下\(K\)个人。
已知小S的编号是Id,问按照小S的方法来他有多少的概率可以不被踢出,成功得到看电影的机会。

要求你用最简真分数的形式表示概率。
继续阅读 [JZOJ4745]看电影

0