首先，基本的函数只有两种：整体乘法和单点加法；我们将其称作“原子函数”，而其它函数都是这两种函数的复合，称作“复合函数”。 注意到任意一个复合函数 fff 都可以表示成如下的形式 f(x)=kx+bf(x)=kx+b f(x)=kx+b 其中x,b∈Rn,k∈Rx,b\in R^n,k \in Rx,b∈Rn,k∈R 现在考虑多个复合函数要如何计算，以三个函数的复合为例，设 f1(x)=k1x+b1f2(x)=k2x+b2f3(x)=k3x+b3f_1(x)=k_1x+b_1\\ f_2(x)=k_2x+b_2\\ f_3(x)=k_3x+b_3 f1 (x)=k1 x+b1 f2 (x)=k2 x+b2 f3 (x)=k3 x+b3 则 f3(f2(f1(x)))=k3k2k1x+k3k2b1+k3b2+b3f_3(f_2(f_1(x)))=k_3k_2k_1x+k_3k_2b_1+k_3b_2+b_3 f3 (f2 (f1 (x)))=k3 k2 k1 x+k3 k2 b1 +k3 b2 +b3 一般地 从上式中可以看出，若干个复合函数的 kkk 就等于各项的 kjk_jkj 的乘积，而复合函数的 b\bold bb 的计算比较复杂,如果暴力计算,将会有O(n2)O(n^2)O(n2) 的时间复杂度,这也是该题算法设计的瓶颈所在。 现在来考虑如何计算复合函数的加法项 b\bold bb。重新审视 该式中bj\bold b_jbj 的系数为∏l=j+1nkj\prod_{l=j+1}^nk_j∏l=j+1n kj ,这也相当于把fj\bold f_jfj 的加法部分重复执行了 ∏l=j+1nkj\prod_{l=j+1}^n k_j∏l=j+1n kj 次。也就是说,如果(fn∘⋯∘f1)(\bold f_n\circ\cdots\circ\bold f_1)(fn ∘⋯∘f1 )被执行了 111 次,那么fj\bold f_jfj 的加法就会被执行∏l=j+1nkj\prod_{l=j+1}^nk_j∏l=j+1n kj 次。而fj\bold f_jfj 又是其它函数的复合，于是这个系数可以 push_down 下去，就像线段树中加法的 lazy_tag 一样。push_down 的过程直到原子函数终止。 根据题意，所有的函数调用会构成一个 DAG。即：如果函数 f\bold ff 调用了函数 g\bold gg，那么就从 f\bold ff 到g\bold gg连一条有向边 对于每个函数的 kkk，我们可以用记忆化搜索求解 现在我们来考虑如何 push_down 每个函数的加法标记，首先，对于直接调用的 qqq 个函数，它们的加法标记会反向传播（我们可以在这个过程中顺便计算全局乘法） 然后，对于函数调用构成的 DAG，可以使用拓扑排序来 push_down 加法标记 完整AC代码 > 欢迎加入团队！！！

代码有点长，别介意。。。

把每个操作和它所执行的操作连单向边，这样就形成了一个 dag。 在这个 dag 上面，真正使答案变化的是那些出度为 0 的点，其他点只是反复地"调用"它们。 那么不难联想到要处理出每一个点所能产生的贡献。 我们发现，对于乘法操作，越靠后进行它影响的范围就越广，而在它之前的所有操作，都受这个乘法的影响。 这样可以沿拓扑序倒序递推出每个节点的贡献，这里的贡献指进行这个操作，整个序列要乘以多少。 接下来我们再考虑加法操作。 同理，我们可以维护出对于每个操作，它在这个操作串中被加了多少次。 注意：这时我们就要整体考虑了，并且对于 op≠1 的那些操作，我们递推不是为了统计答案，而是要得到后面状态的值。 很显然，我们要顺着拓扑序去更新。 此时也要把乘法标记下放，最后先乘再加，以防搞混。