某岛

… : "…アッカリ~ン . .. . " .. .
November 7, 2014

Codeforces Round #232

http://codeforces.com/contest/396
http://user.qzone.qq.com/251815992/blog/1393572631

Problem A. On Number of Decompositions into Multipliers

Brief description:

给定一个数,问分拆成 n 个整数乘积的方案有多少种。

Analysis:

。。每个素因子是独立的。。乘法原理。。
考察某个素因子,假设出现了 m 次。。那么就是将 m 个球放进 n 个盒子中的方案数。。。
隔板法即可。

Problem B. On Sum of Fractions

Brief description:

。。

Analysis:

裂项。

Problem C. On Changing Tree

Brief description:

给出一棵有根树,支持以下两种操作:

  • 1 u a k:表示对以 u 为根的子树,对每个结点添加 a-dk,其中 d 是该结点与 v 的距离。
  • 2 u:查询节点 v 的值。

Analysis:

。如果 d = 0。。那么显然就是。。
http://www.shuizilong.com/house/archives/poj-3321-apple-tree/

这里我们只需要维护两个树状数组 c1, c2
每次修改时。。
。。对 c1 += a ,c2 += d。。。
询问时返回 c1 – dep[v]*c2 。。。
(这样会多减去一点。。再从 c1 里加上。。。)

http://codeforces.com/contest/396/submission/5971492