P3673 小清新计数题

    • 9通过
    • 51提交
  • 题目提供者fjzzq2002
  • 标签 枚举,暴力 环套树 生成树 洛谷原创 O2优化 高性能
  • 难度 省选/NOI-
  • 时空限制 1s / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 推荐的相关题目

    题目描述

    小A正在电脑上玩一个叫做Truth or Lie的游戏。

    游戏开始时电脑会给出n句话,每句话形如“第x句话为真”或“第x句话为假”,其中x是一个1到n的整数,你只要选择“Good”或者“Bad”,“Good”表示可以决定每句话的真假使每句话的内容都成立,“Bad”反之。

    作为一个菜鸡,小A只会不停地点“Good”,靠脸过关。

    在无数次失败后,非洲人小A发现游戏每关中,每句话包含的是“真”还是“假”是固定的,但是每句话中的x是在1到n均匀随机的。

    现在小A告诉了你某一关每句话的真假,用一个01序列表示。第i位为0表示第i句话包含“假”,否则表示包含“真”。现在他想要知道使得点击“Good”正确的方案数。

    由于方案数可能比较大,你需要输出方案数对998244353取模的结果。

    (读不懂题的请移步样例解释)

    输入输出格式

    输入格式:

    一行一个01序列,它的长度即为n。

    输出格式:

    输出方案数对998244353取模的结果。

    输入输出样例

    输入样例#1: 复制
    01
    输出样例#1: 复制
    1
    输入样例#2: 复制
    10101
    输出样例#2: 复制
    1154
    输入样例#3: 复制
    10101101010111110100110100101010110001010010101001
    输出样例#3: 复制
    322173207

    说明

    样例解释

    第一句话的内容为“某句话为假“,第二句话的内容为“某句话为真”。所有可能情况如下:

    1. 第一句话的内容为“第一句话为假”,第二句话的内容为“第一句话为真”,结果应为Bad。

    2. 第一句话的内容为“第一句话为假”,第二句话的内容为“第二句话为真”,结果应为Bad。

    3. 第一句话的内容为“第二句话为假”,第二句话的内容为“第一句话为真”,结果应为Bad。

    4. 第一句话的内容为“第二句话为假”,第二句话的内容为“第二句话为真”,结果应为Good,因为只需认为第一句话为假,第二句话为真就符合两句话,所以是Good。

    所以共有一种合法方案。

    数据范围

    对于10%的数据,$n \leq 7$。

    对于20%的数据,$n \leq 9$。

    对于60%的数据,$n \leq 20$。

    对于100%的数据,$1 \leq n \leq 50$。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。