#P5645. [PKUWC2018] 斗地主

[PKUWC2018] 斗地主

题目背景

斗地主是一种使用黑桃、红心、梅花、方片的A到K加上大小王的共54张牌来进行的扑克牌游戏,其中大小王各一张,其他数码牌各四张。在斗地主中,牌的大小关系根据牌的数码表示如下:3<4<5<6<7<8<9<10<J<Q<K<A<2<3<4<5<6<7<8<9<10<J<Q<K<A<2< 小王 << 大王,而花色并不对牌的大小产生影响。每一局游戏中,一副手牌由 nn 张牌组成。游戏者每次可以根据规定的牌型进行出牌,首先打光自己的手牌一方取得游戏的胜利。为了简化题目,本题不考虑花色的影响,即所有的相同的数码的牌都是被视为一样的

在这道题中,允许的出牌牌型有(这一部分与传统的斗地主有所出入,请注意):

名称 解释 举例
火箭 双王 ♂♀
炸弹 相同数码的四张牌 6666
单牌 单独的一张牌 6 单张的王也是单牌
对子 相同数码的两张牌 66 大小王不是对子
三张牌 相同数码的三张牌 666
三带一 相同数码的三张牌带上一张另外数码的单牌 666♂ 炸弹不是三带一
三带二 相同数码的三张牌带上一个另外数码的对子 66699
顺子 牌的大小连续的 55 张及以上单牌 3456789 不能含有大小王和2
连对 牌的大小连续的 33 对及以上的对子 33445566
三顺 牌的大小连续的两组及以上的三张牌 333444555
四带二 四张相同数码的牌带上两张单牌 444456 444455
飞机(单翅膀) 三顺带上相同数量的数码两两不同的单牌 33344455569J
飞机(双翅膀) 三顺带上相同数量的数码两两不同的对子 3334446699

注意

  1. 在牌型中没有连炸这种牌型,但是形如 444455556666 的牌仍然是能出的,它将被视为 444555666 带 456 的飞机(单翅膀)牌型。
  2. 大王和小王数码不同,即飞机带大小王是合法的,例如 333444♂♀
  3. 容易验证,上述牌型的规则是合法的,即对于任意合法的牌,它都有唯一的牌型。

两手牌是属于相同牌型的当且仅当他们的名称相同且包含牌的数量相同。相同牌型的牌之间存在着大小关系(火箭是唯一的,不需要比大小):

  1. 三带一三带二的大小取决于那三张相同牌的数码
  2. 飞机的大小取决于三顺的大小
  3. 四带二的大小取决于四张相同牌的大小
  4. 其他牌型的大小取决于牌中的最大的一张牌

下面是对斗地主的游戏过程的描述(这一部分与传统的斗地主完全相同):

  1. 在斗地主中,有玩家被分成了两个阵营,一个玩家是地主,剩下两个玩家是农民。地主有 2020 张牌,农民每人有 1717 张牌(加起来正好是一副牌)。
  2. 游戏分成若干轮,每一轮由上一轮的胜者率先出牌(第一轮由地主最先出牌)。接着按照顺序(你可以理解为三个玩家坐成一圈,按照顺时针顺序)出牌。
  3. 每一轮第一个出牌的玩家可以出任意牌型任意大小的牌。接着轮到每一个玩家出牌时,他有如下选择:
    1. 不出(过牌)
    2. 出与这一轮中上一次被打出的牌相同牌型但是大小严格更大的牌
    3. 如果上一次被打出的牌不是炸弹或者火箭,那么可以打出任意大小的炸弹
    4. 打出火箭
  4. 在一轮中,如果在一个玩家打出牌后,另外两个玩家都选择不出,那么这一轮结束,这一个玩家作为本轮的胜者并开始下一轮
  5. 任何时刻如果一个玩家的所有手牌都已打出,那么游戏结束,这一个玩家获胜。
  6. 如果地主获胜时,两个农民都一张牌都没有打出,那么就称地主打出了春天。

题目描述

现在三个人在玩斗地主,如果地主春天了,那么算地主赢,否则即使地主先出完了牌,也视为农民赢。假设三个玩家都以最优决策在行动。

现在给出了 n(0n20)n(0 \leq n\leq 20) 张牌,问地主有多少种初始手牌包含了这 nn 张牌,且无论农民的牌如何,他都一定能春天。

输入格式

第一行一个整数 tt 表示数据组数。

每组数据输入一行,第一个整数 nn 表示固定了的牌数,接下来 nn 个空格隔开的整数描述每一张固定了的手牌。

特别的,我们用 11 来表示数码 A, 1111 表示数码 J, 1212 表示数码 Q, 1313 表示数码 K,1414 表示小王,1515 表示大王。保证输入一定合法,即每种牌的数量不会超出一副牌中牌的数量。

输出格式

对于每组数据,输出一个整数表示答案,满足条件的地主的手牌数。答案可能很大,请对 998244353998244353 取模后输出。

注意,在这题中我们不考虑花色,如果两种手牌的数码组成完全相同,但是花色不同,他们也是会被视为同一种的。

6
20 1 2 2 3 4 5 6 7 8 8 9 10 11 11 12 13 13 13 13 15
20 1 1 2 2 3 4 5 6 7 8 9 10 11 12 12 12 12 13 13 14
20 1 2 2 3 3 4 5 6 7 7 7 7 8 9 10 10 11 12 13 15
20 1 2 3 4 4 5 6 7 8 9 10 11 11 12 13 13 13 13 14 15
3 3 3 3
4 3 3 3 3
1
0
1
1
4790
1670

提示

样例解释

对于第一组样例,可以发现农民不可能有炸弹或者火箭,所以可以先打[3,4,5,6,7,8,9,10,J,Q][3,4,5,6,7,8,9,10,J,Q](显然其他农民都要不起),然后打[2,2][2,2],再打大王,然后打[K,K,K,K,A,J][K,K,K,K,A,J],最后打[8][8]

ID nn tt
1 =20=20 =100= 100
2 =18=18
3 =16=16
4 =14=14
5 =12=12
6 =0=0 =1= 1
7
8 [0,20]\in [0,20] =500= 500
9 =1000= 1000
10 =2000= 2000