Project Euler | 欧拉计划
0%

Problem 696

题目发布于 翻译更新于

Problem 696

Mahjong

The game of Mahjong is played with tiles belonging to $s$ suits. Each tile also has a number in the range $1\ldots n$, and for each suit/number combination there are exactly four indistinguishable tiles with that suit and number. (The real Mahjong game also contains other bonus tiles, but those will not feature in this problem.)

A winning hand is a collection of $3t+2$ Tiles (where $t$ is a fixed integer) that can be arranged as $t$ Triples and one Pair, where:

  • A Triple is either a Chow or a Pung
  • A Chow is three tiles of the same suit and consecutive numbers
  • A Pung is three identical tiles (same suit and same number)
  • A Pair is two identical tiles (same suit and same number)

For example, here is a winning hand with $n=9$, $s=3$, $t=4$, consisting in this case of two Chows, two Pungs, and one Pair:

A winning Mahjong hand

Note that sometimes the same collection of tiles can be represented as $t$ Triples and one Pair in more than one way. This only counts as one winning hand. For example, this is considered to be the same winning hand as above, because it consists of the same tiles:

Alternative arrangement of the same hand

Let $w(n, s, t)$ be the number of distinct winning hands formed of $t$ Triples and one Pair, where there are $s$ suits available and tiles are numbered up to $n$.

For example, with a single suit and tiles numbered up to $4$, we have $w(4, 1, 1) = 20$: there are $12$ winning hands consisting of a Pung and a Pair, and another $8$ containing a Chow and a Pair. You are also given that $w(9, 1, 4) = 13259$, $w(9, 3, 4) = 5237550$, and $w(1000, 1000, 5) \equiv 107662178 \pmod{1\ 000\ 000\ 007}$.

Find $w(10^8, 10^8, 30)$. Give your answer modulo $1\ 000\ 000\ 007$.

麻将

变种麻将游戏需要用到$s$种花色、牌面数字为$1\dots n$、每种花色/数字组合各四张的麻将牌。（现实中的标准麻将还会用到花牌和字牌，但在本问题中不考虑这些。）

和牌是一手共$3t+2$张牌（其中$t$是预先确定的整数），且这些牌能够被排列为$t$组加一对，其中：

  • 一组可以是一个顺子或者一个刻子
  • 顺子是指三张花色相同、数字连续的牌
  • 刻子是指三张花色/数字组合完全相同的牌
  • 一对是指两张花色/数字组合完全相同的牌

如下所示就是当$n=9$，$s=3$，$t=4$（即标准麻将）时的一手和牌，包括两个顺子、两个刻子和一对：

一手麻将和牌

注意到，相同的一手麻将牌可以有多种方式表示为$t$组和一对，但这只被算作一手和牌。例如，如下所示就是和上图相同的一手和牌：

同一手和牌的不同表示

当共有$s$种花色、牌面数字至多为$n$时，记$w(n, s, t)$为所有由$t$组和一对构成的不同和牌的数量。

例如，如果只有一种花色，且数字至多为$4$，我们有$w(4, 1, 1) = 20$：有$12$手包括一个刻子和一对，还有$8$手包括一个顺子和一对。已知$w(9, 1, 4) = 13259$，$w(9, 3, 4) = 5237550$，$w(1000, 1000, 5) \equiv 107662178 \pmod{1\ 000\ 000\ 007}$。

求$w(10^8, 10^8, 30)$并将你的答案对$1\ 000\ 000\ 007$取余。