QOJ.ac

QOJ

Süre Sınırı: 1 s Bellek Sınırı: 256 MB Toplam puan: 100

#20297. 傳奇遊戲

İstatistikler

有個玩著頂級手機遊戲的人,某天在試圖簽署合約時,對自己必須玩的遊戲非常生氣。遊戲規則如下:

  • 有一個牌池,包含編號從 $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.