P1310 表达式的值

    • 497通过
    • 1.5K提交
  • 题目提供者 CCF_NOI
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 字符串 NOIp普及组 2011
  • 难度 普及+/提高
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    对于1 位二进制变量定义两种运算:

    运算的优先级是:

    1. 先计算括号内的,再计算括号外的。

    2. “× ”运算优先于“⊕”运算,即计算表达式时,先计算× 运算,再计算⊕运算。例如:计算表达式A⊕B × C时,先计算 B × C,其结果再与 A 做⊕运算。

    现给定一个未完成的表达式,例如_+(_*_),请你在横线处填入数字0 或者1 ,请问有多少种填法可以使得表达式的值为0 。

    输入输出格式

    输入格式:

    输入文件名为exp.in ,共 2 行。

    第1 行为一个整数 L,表示给定的表达式中除去横线外的运算符和括号的个数。

    第2 行为一个字符串包含 L 个字符,其中只包含’(’、’)’、’+’、’*’这4 种字符,其中’(’、’)’是左右括号,’+’、’*’分别表示前面定义的运算符“⊕”和“×”。这行字符按顺序给出了给定表达式中除去变量外的运算符和括号。

    输出格式:

    输出文件exp.out 共1 行。包含一个整数,即所有的方案数。注意:这个数可能会很大,请输出方案数对10007 取模后的结果。

    输入输出样例

    输入样例#1: 复制
    4
    +(*)
    
    输出样例#1: 复制

    说明

    【输入输出样例说明】

      给定的表达式包括横线字符之后为:_+(_*_) 

      在横线位置填入(0 、0 、0) 、(0 、1 、0) 、(0 、0 、1) 时,表达式的值均为0 ,所以共有3种填法。 

    【数据范围】

    对于20% 的数据有 0 ≤ L ≤ 10。

    对于50% 的数据有 0 ≤ L ≤ 1,000。

    对于70% 的数据有 0 ≤ L ≤ 10,000 。

    对于100%的数据有 0 ≤ L ≤ 100,000。

    对于50% 的数据输入表达式中不含括号。

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