QOJ.ac

QOJ

Limite de temps : 1 s Limite de mémoire : 256 MB Points totaux : 100

#20297. 传奇游戏

Statistiques

某位玩着顶尖手机游戏的人,有一天在试图签订合同时,对不得不玩的游戏非常生气。这个游戏的规则如下:

  • 有一个牌池,其中的数字为 $1$ 到 $2N+K$。
  • 游戏会从牌池中依次抽取 $N$ 张牌(不放回,即同一个数字不能被抽到两次)。
  • 在抽牌之后,玩家猜测下一张牌的数字会更大还是更小。

让玩家生气的是,由于运气不好,较小的数字后面总是出现更小的数字,而较大的数字后面总是出现更大的数字。于是,玩家希望通过修改游戏的随机机制来避免这种情况。他对抽牌过程增加了以下两条规则:

  • 如果抽到的牌上的数字在 $1$ 到 $N$ 之间,那么下一张抽到的牌上的数字必须严格大于 $N$($>N$)。
  • 如果抽到的牌上的数字在 $N+K+1$ 到 $2N+K$ 之间,那么下一张抽到的牌上的数字必须严格小于 $N+K+1$($<N+K+1$)。

玩家想知道这些修改对游戏造成了多大的破坏。衡量破坏程度的指标是:修改后的游戏中所有可能的不同抽牌序列的数量,与正常游戏中所有可能的抽牌序列的数量之比。他请你求出这个比值对 $10^9+7$ 取模的结果。

实现细节

你需要实现以下函数:

int oyun(int N, int K)
  • $N$ 和 $K$ 是整数,按题目描述确定牌池和抽取的牌的数量。
  • 该函数应返回所要求的比值。
  • 在每个测试中,该函数恰好被调用一次。

数据范围

  • $1\le N\le 10^6$。
  • $1\le K\le 100$。

子任务

子任务 分值 附加限制 依赖子任务
1 10 $1\le N,K\le 6$ —
2 18 $1\le N\le 100$ 1
3 6 $1\le N\le 1000$ 1, 2
4 47 $1\le N\le 10^4$ 1, 2, 3
5 19 无附加限制 1, 2, 3, 4

样例

oyun(2, 1)

上面的函数调用应返回 $600000005$。

牌上的数字为 $1,2,3,4,5$。我们将抽取 2 张牌。在正常情况下,有 $20$ 种不同的抽牌方式。在修改后的游戏中,如果第一张牌是 $1$、$2$、$4$ 或 $5$,第二张牌有 3 种不同的可能;如果第一张牌是 $3$,第二张牌有 4 种不同的可能。因此,修改后的游戏总共有 $16$ 种可能。$\frac{16}{20}=\frac45$。在所使用的模数下,这个概率对应 $600000005$。

样例评测程序

样例评测程序要求每个测试用例按以下格式输入:

$$N\ K$$

如果所要求的函数成功返回一个整数,评测程序将按以下格式输出该结果 $R$:

$$R$$

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#2824EditorialOpenNew Editorial for Problem #20297louyuxuanView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.