TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P6407
  • 题目
  • P6407[CSP-S 2019 Day2]Emiya家今天的饭
    限制 : 时间限制 : 25000 MS   空间限制 : 262144 KB
    评测说明 : 1s,256MB
    问题描述

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

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

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

    • Emiya不会让大家饿肚子,所以将做至少一道菜,即$k\geq1$
    • Rin希望品尝不同烹饪方法做出的菜,因此她要求每道菜的烹饪方法互不相同
    • Yazid不希望品尝太多同一食材做出的菜,因此他要求每种主要食材至多在一半的菜(即$\lfloor k/2\rfloor$道菜)中被使用。(这里的$\lfloor x\rfloor$为下取整函数,表示不超过$x4的最大整数)

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

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

    输入格式

    第1行两个用单个空格隔开的整数$n,m$。

    第2行至第$n+1$行,每行$m$个用单个空格隔开的整数,其中第$i+1$行的$m$个数依次为$a_{i,1},a_{i,2},\dots,a_{i,m}$。

    输出格式

    仅一行一个整数,表示所求方案数对$998,244,353$取模的结果。

    样例输入 1

    2 3
    1 0 1
    0 1 1

    样例输出 1

    3

    样例输入 2

    3 3
    1 2 3
    4 5 0
    6 0 0

    样例输出 2

    190

    样例输入 3

    5 5
    1 0 0 1 1
    0 1 0 1 0
    1 1 1 1 0
    1 0 1 0 1
    0 1 1 0 1

    样例输出 3

    742

    提示

    样例1解释

    由于在这个样例中,对于每组$i,j$,Emiya都最多只会做一道菜,因此我们直接通过给出烹饪方法、主要食材的编号来描述一道菜。

    符合要求的方案包括:

    • 做一道用烹饪方法1、主要食材1的菜和一道用烹饪方法2、主要食材2的菜
    • 做一道用烹饪方法1、主要食材1的菜和一道用烹饪方法2、主要食材3的菜
    • 做一道用烹饪方法1、主要食材3的菜和一道用烹饪方法2、主要食材2的菜

    因此输出结果为$3\mod{998,244,353=3}$。需要注意的是,所有只包含一道菜的方案都是不符合要求的,因为唯一的主要食材在超过一半的菜中出现,这不满足Yazid的要求。

    样例2解释

    Emiya必须至少做$2$道菜。

    • 做2道菜的符合要求的方案数为100。
    • 做3道菜的符合要求的方案数为90。

    因此符合要求的方案数为100+90=190。

    数据范围

    测试点编号 \(\qquad\) \(n=\) \(\qquad\) \(m=\) \(\qquad\) \(a_{i,j}<\)
    1 2 2 2
    2 2 3 2
    3 5 2 2
    4 5 3 2
    5 10 2 2
    6 10 3 2
    7 10 2 1000
    8 10 3 1000
    9~12 40 2 1000
    13~16 40 3 1000
    17~21 40 500 1000
    22~25 100 2000 998,244,353

    对于所有测试点,保证$1\leq n\leq 100,\quad 1\leq m\leq 2000,\quad 0\leq a_{i,j}<998,244,353$。