COWBASIC

题目描述

Bessie 发明了一种新的编程语言，但由于还没有编译器，她需要你帮助她实际运行她的程序。 COWBASIC 是一种简单而优雅的语言。它有两个关键特性：加法和 MOO 循环。Bessie 为溢出问题设计了一个巧妙的解决方案：所有加法都在模 $10^9+7$ 意义下进行。但 Bessie 真正的成就是 MOO 循环，它会将一段代码块重复执行固定次数。当然，MOO 循环与加法都可以嵌套。 给定一个 COWBASIC 程序，请帮助 Bessie 确定它最终返回的数字。

输入格式

（文件 cowbasic.in）： 给定一个最多 100 行的 COWBASIC 程序，每行最多 350 个字符。一个 COWBASIC 程序由一系列语句组成。 共有三种语句： =

MOO { }

RETURN 共有三种表达式：

( ) + ( ) 其中，literal 为不超过 100,000 的正整数。 variable 为长度不超过 10 的小写英文字母串。 保证任何变量在被使用或被 RETURN 之前都已被定义。 保证 RETURN 恰好出现一次，并且在程序的最后一行。

输出格式

（文件 cowbasic.out）： 输出一个正整数，表示被 RETURN 的变量的值。

x = 1
10 MOO {
  x = ( x ) + ( x )
}
RETURN x

1024

n = 1
nsq = 1
100000 MOO {
  100000 MOO {
    nsq = ( nsq ) + ( ( n ) + ( ( n ) + ( 1 ) ) )
    n = ( n ) + ( 1 )
  }
}
RETURN nsq

4761

提示

Scoring 在 20% 的测试用例中——MOO 循环不嵌套。 在另外 20% 的测试用例中——程序只有 1 个变量，MOO 循环可以嵌套。 在剩余的测试用例中，没有进一步限制。 这个 COWBASIC 程序计算 $2^{10}$。 这个 COWBASIC 程序计算 $(10^5*10^5+1)^2$（模 $10^9 + 7$）。 题目贡献：Jonathan Paulson

标签: USACO|2017|Platinum

来源

USACO|2017|Platinum