表达式计数解题报告

1、表达式计数 解题江苏苏州中学1，题目描述【问题描述】有一些表达式本质上是相同的，如 a+(b-c), (a+b)-c。你的任务是统计出 N 元的不同表达式有多少个。为使问题简单些，只有+-*/和括号是允许的。【输入文件】一个整数N，意义如上描述。【输出文件】一个整数表示表达式个数。因为可能很大，只需输出对 1,000,000,007 取模后的值。【输入样例】4【输出样例】1170【数据规模和约定】100%的数据中 N30；2，观察先来观察几个表达式：(a+b)*(c+d-e)*(f-g+h)a*(b-c)+d/(e-f)-g*h*i a+b+c-d+e+f+g*h13，初步分析表达式可以按照最

2、后一步进行的是加减还是乘除分成两类：1， 加减：a*(b-c)+d/(e-f)-g*h*i 和a+b+c-d+e+f+g*h 2， 乘除：(a+b)*(c+d-e)*(f-g+h)先来看第一类，由于最后进行的是加减运算可以用最后进行的几个加减运算符把算式分割成若干段。+-想，这各部分直接是不是可以独立运算，然后方案数相乘呢？这是不正确的，比如：(a-b)(b-a)*(c-d)*(d-c)这两个算式是本质相同的，但是会把它们算成两种不同的方案，这是为什么呢？因为，由乘号分割开的两部分是会互相影响的。在这里出现了一点小问题，由于这个问题是因为减号而导致的，所以化一下问题：只用加减乘号来捉，看看怎么

3、捉？先简4，简化由于简化版不带有减号，很容易想到按照最后一步运算是加法还是乘除法进行分类。为了呆会儿扩展的时候方便，进行计算。把加号的个数也作为状态，设 fij表示使用 i 个字母，j 个加号且最后一步的运算是加法的表达式数目。设gij表示使用i 个字母，j 个加号且最后一步的运算是乘除的表达式数目。状态转移：枚举所有i 的自然数无序拆分，然后计算在当前拆分的情况下方案数是多少。举个例子来说，比如计算 g31。首先枚举 3 的正整数拆分，比如：3=1+2把加号分配到两部分中去，有 2 种方案，1， 分配到第一部分中去，f11*f20=02， 分配到第二部分中去，f10*f21=1分开：然后，然

4、后，需要把 3 个字母分配到两个部分中去，这个方案数是 3。用一个乘除号来连接这两部分的方案数是 22-1=3。所以g31在 3=1+2 这个拆分情况下的方案数是(0+1)*3*3=9。以上状态转移涉及到了三个子问题：1， 如何分配加号？2， 有 n 个不同的球，放到 k 个总容量和为 n 的盒子中去，他们的容量分别是a1，a2，a3.ak，容量相同的盒子是不可区分的。在这种情况下的方案数。对于第一个问题，可以用一个 O(n2)的动态规划来解决。2g*h*id/(e-f)a*(b-c)对于第二个问题，可以用组合数公式来解决：n！1方案数 *！ 第一种盒子的数目！* 第二种盒子的数目！*.a ！* a ！*.* a12k3， 用k 个乘除号连接 k+1 个部分的方案数为 2k+1-1。就可以在 O(无序拆分(n)*n3)的时间内解决了。于是这个简化版5，回到原题因为，原题可以用减号，而加减号的影响又是全局的，这似乎使原问题复杂了很多。但是，注意到由于影响是全局的，所以由加减号造成的表达式不相同的方案数只和总的使用的加减号数目有关。就比如说把表达式(a+b)*(c+d)中的加号，允许替换成加减号，所得到的本质不同的表达式数目是 7 种。把表达式a+b+c*d 中的加号，允许替换成加减号，所得到的本质不同的表达式数目是 7 种。更进一步，如果有 k 个加号，那么如果