P4996 咕咕咕

    • 619通过
    • 2.9K提交
  • 题目提供者 fstqwq 管理员
  • 评测方式 云端评测
  • 标签 状态压缩,状压 进制 递推
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    小 F 是一个能鸽善鹉的同学,他经常把事情拖到最后一天才去做,导致他的某些日子总是非常匆忙。

    比如,时间回溯到了 2018 年 11 月 3 日。小 F 望着自己的任务清单:

    1. 看 iG 夺冠;
    2. 补月赛题的锅。

    小 F 虽然经常咕咕咕,但他完成任务也是很厉害的,他一次性可以完成剩余任务的任一非空子集。比如,他现在可以选择以下几种中的一种:

    1. 看 iG 夺冠;
    2. 补月赛题的锅;
    3. 一边看 iG 夺冠的直播,一边补锅。

    当然,比赛实在是太精彩了,所以小 F 就去看比赛了。

    不过,当金雨从天而降、IG 举起奖杯之时,小 F 突然心生愧疚——锅还没补呢!于是,小 F 的内心产生了一点歉意。

    这时小 F 注意到,自己总是在某些情况下会产生歉意。每当他要检查自己的任务表来决定下一项任务的时候,如果当前他干了某些事情,但是没干另一些事情,那么他就会产生一定量的歉意——比如,无论他今天看没看比赛,只要没有补完月赛的锅,他都会在选择任务的时候产生 $1$ 点歉意。小 F 完成所有任务后,他这一天的歉意值等于他每次选择任务时的歉意之和。

    过高的歉意值让小 F 感到不安。现在,小 F 告诉你他还有 $n$ 项任务,并告诉你在 $m$ 种情况中的一种 $\mathrm{state}_i$ 的情况下,小 F 会产生 $a_i$ 点歉意。请你帮忙计算一下,小 F 在那一天所有可能的完成所有任务方式的歉意值之和是多少。

    由于答案可能很大,你只需要输出答案对 $998244353$ 取模即可。

    输入输出格式

    输入格式:

    输入一行两个整数 $n, m$,表示有 $n$ 项任务,在 $m$ 种情况中下小 F 会产生歉意值。

    输入接下来 $m$ 行,每行有一个长度为 $n$ 的 $0-1$ 串 $\mathrm{state}_i$ 和一个歉意值 $a_i$,$\mathrm{state}_{i, j}$ 为 $0/1$ 表示第 $j$ 项任务此时没做 / 已经做了。

    详情请参考样例和样例解释。

    输出格式:

    输出一行一个整数,表示小 F 在那一天所有可能的完成任务方式的歉意值之和对 $998244353$ 取模的结果。

    输入输出样例

    输入样例#1: 复制
    2 2
    00 1
    10 1
    输出样例#1: 复制
    4
    输入样例#2: 复制
    3 4
    000 16
    001 9
    110 4
    111 1
    输出样例#2: 复制
    260

    说明

    样例 1 解释:

    $0-1$ 串中第一个数字表示小 F 看没看比赛,第二个数字表示小 F 补没补锅。

    我们用 $\varnothing$ 表示小 F 什么都没干,$A$ 表示小 F 看了比赛,$B$ 表示小 F 补了锅,那么所有会产生愧疚的方式如下:

    $\varnothing: 1$
    $\{A\}:1$

    那么所有可能的选择如下:

    $\varnothing\rightarrow\{A\}\rightarrow\{A,B\}:2$
    $\varnothing\rightarrow\{B\}\rightarrow\{A,B\}:1$
    $\varnothing\rightarrow\{A,B\}:1$

    所以答案是 $2 + 1 + 1 = 4$。

    数据范围

    保证出现的 $\mathrm{state}_i$ 互不相同。

    对于所有数据,有 $1 \leq n \leq 20$, $1 \leq m \leq \min(2 ^ n, 10 ^ 5), 1 \leq a_i \leq 10 ^ 5$。

    Case $n$
    1 $1$
    2 $2$
    3 $3$
    4 $10$
    5 $12$
    6 $14$
    7 $16$
    8 $18$
    9 $19$
    10 $20$
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。