#6434. 「PKUSC2018」主斗地

内存限制:512 MiB 时间限制:4000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: l0nl1f3

题目描述

如果你参加过 NOIP 2015 和 PKUWC 2018,那么你一定对一道叫做斗地主的题印象深刻。为了致敬经典,我们又出了一道有关打牌的题。在本题中,牌型和斗地主类似但不完全相同,我们称本题中的扑克游戏为主斗地。

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

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

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

注意

  1. 在牌型中没有连炸这种牌型,但是形如 444455556666 的牌仍然是能出的,它将被视为 444555666 带 456 的飞机(单翅膀)牌型。
  2. 大王和小王数码不同,即飞机带大小王是合法的,例如 333444wW
  3. 容易验证,上述牌型的规则是合法的,即对于任意合法的牌,它都有唯一的牌型。
  4. 在牌型中,没有炸弹。炸弹将被视为三带一,且没有炸弹的效果,即它不能压任何牌型。
  5. 在牌型中,没有火箭。这意味着 wW 不再是一个合法的牌型。

两手牌是属于相同牌型的当且仅当他们的名称相同且包含牌的数量相同。相同牌型的牌之间存在着大小关系:

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

下面是对主斗地的游戏过程的描述:

  1. 在主斗地中,有两个玩家,他们是同一个阵营的,两个玩家要一同达成游戏目标。为了方便,我们假设第一个玩家是九条可怜,第二个玩家是××网友。
  2. 游戏只会使用一副完整的扑克牌。在游戏开始的时候,会先把所有的 33 扔掉。之后双方各从这一副牌中随机抽取 1717 张,余下的 1616张被丢弃。你可以认为是随机洗牌后,九条可怜取前 1717 张,××网友后 1717 张,剩下的 1616 张被掉了。
  3. 游戏分成若干轮,每一轮分为两步:
    1. 第一步,九条可怜从当前手牌中选择一个任意牌型任意大小的牌 CC 并打出。
    2. 第二步,××网友从当前手牌中选择一个和 CC 牌型相同且大小 严格更大 的牌 CC' 打出。如果不存在这样的牌则游戏失败。
  4. 在某一轮结束后,如果九条可怜和××网友中有至少一个人没有手牌,则游戏结束。如果两个人都没有手牌,则游戏胜利,否则游戏失败。

下面是一个例子:

假设九条可怜的牌是 44445556789TJQKwW,××网友的牌是 666789TJQKAAAA222。那么一个可以获胜的方案是:

  1. 第一轮九条可怜出 4444wW,××网友出 AAAA22。
  2. 第二轮九条可怜出 6789TJQ,××网友出 789TJQK。
  3. 第三轮九条可怜出 555K,××网友出 6662。

这个游戏很考验两个玩家之间的默契。但是因为九条可怜和××网友无法相互理解,于是他们打算以明牌的方式进行游戏,即双方都知道对方的牌。因为两个人都会按照最优策略行动,所以在牌下发的时候,游戏的胜负就已经确定了。

现在给出××网友的牌,你需要计算九条可怜有多少种不同的可能的手牌可以获得胜利。

注意:××网友和九条可怜的牌都来自于同一副扑克,且分牌的时候没有 33

输入格式

每组数据输入一行,一个长度为 1717 的字符串表示××网友的牌。我们用 456789TJQKA2wW 来表示每一种牌。

输出格式

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

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

样例

样例输入

556789TJJQKKAA22w
456789TJJQKKAA22w
456789TJQKKKAAA22

样例输出

193483
0
613897

数据范围与提示

因为种种原因,本题采用捆绑测试,一共有 33 个 subtask:

子问题编号 分值 约定
1 3030 每一种牌最多出现 22
2 3030 每一种牌最多出现 33
3 4040 每一种牌最多出现 44

时间限制:2s

空间限制:512M