#2096. 「CSP-S 2019」Emiya 家今天的饭

内存限制:256 MiB 时间限制:1000 ms 输入文件:meal.in 输出文件:meal.out
题目类型:传统 评测方式:文本比较
上传者: StudyingFather

题目描述

Emiya 是个擅长做菜的高中生,他共掌握 n 烹饪方法,且会使用 m 主要食材做菜。为了方便叙述,我们对烹饪方法从 1 \sim n 编号,对主要食材从 1 \sim m 编号。

Emiya 做的每道菜都将使用恰好一种烹饪方法与恰好一种主要食材。更具体地,Emiya 会做 a_{i,j} 道不同的使用烹饪方法 i 和主要食材 j 的菜 (1\le i\le n, 1\le j\le m) ,这也意味着 Emiya 总共会做 \displaystyle \sum_{i = 1}^n \sum_{j = 1}^m a_{i,j} 道不同的菜。

Emiya 今天要准备一桌饭招待 Yazid 和 Rin 这对好朋友,然而三个人对菜的搭配有不同的要求,更具体地,对于一种包含 k 道菜的搭配方案而言:

  • Emiya 不会让大家饿肚子,所以将做至少一道菜,即 k \ge 1

  • Rin 希望品尝不同烹饪方法做出的菜,因此她要求每道菜的烹饪方法互不相同

  • Yazid 不希望品尝太多同一食材做出的菜,因此他要求每种主要食材至多在一半的菜(即 \lfloor \frac k2 \rfloor 道菜)中被使用

    • 这里的 \lfloor x\rfloor 为下取整函数,表示不超过 x 的最大整数

这些要求难不倒 Emiya,但他想知道共有多少种不同的符合要求的搭配方案。两种方案不同,当且仅当存在至少一道菜在一种方案中出现,而不在另一种方案中出现。

Emiya 找到了你,请你帮他计算,你只需要告诉他符合所有要求的搭配方案数对质数 998,244,353